Last updated on February 20th, 2025 at 08:38 am
Here, we see a Subarray Sum Equals K LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Companies
Level of Question
Medium
Subarray Sum Equals K LeetCode Solution
Table of Contents
1. Problem Statement
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Prefix Sum with Hash Map”. The idea is to use a prefix sum to calculate cumulative sums and a hash map (or dictionary) to store the frequency of these sums. This allows us to efficiently find subarrays with a given sum.
3. Code Implementation in Different Languages
3.1 Subarray Sum Equals K C++
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> mp;
int sum=0,ans=0;
mp[sum] = 1;
for(auto it:nums){
sum += it;
int find = sum - k;
if(mp.find(find) != mp.end()){
ans += mp[find];
}
mp[sum]++;
}
return ans;
}
};
3.2 Subarray Sum Equals K Java
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
int[] sum = new int[nums.length + 1];
sum[0] = 0;
for (int i = 1; i <= nums.length; i++)
sum[i] = sum[i - 1] + nums[i - 1];
for (int start = 0; start < sum.length; start++) {
for (int end = start + 1; end < sum.length; end++) {
if (sum[end] - sum[start] == k)
count++;
}
}
return count;
}
}
3.3 Subarray Sum Equals K JavaScript
var subarraySum = function(nums, k) {
let sum = 0;
let count = 0;
let map = new Map();
map.set(0, 1);
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
let rem = sum - k;
if (map.has(rem)) {
count += map.get(rem);
}
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
};
3.4 Subarray Sum Equals K Python
class Solution(object):
def subarraySum(self, nums, k):
sum = 0
count = 0
map = defaultdict(int)
map[0] = 1
for num in nums:
sum += num
rem = sum - k
if rem in map:
count += map[rem]
map[sum] += 1
return count
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n2) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |