# Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

``````Input:
nums = [1,1,1], k = 2

Output:
2``````

Note:

1. The length of the array is in range [1, 20,000].

2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

## Analysis

Approach 1 - Cumulative sum without space

Instead of considering all the startstart and endend points and then finding the sum for each subarray corresponding to those points, we can directly find the sum on the go while considering different endend points.

Whenever the sumsum equals the required kk value, we can update the countcount value

``if (sum == k) count++;``

Approach 2 - Prefix Sum + Hash Table

If the cumulative sum(repreesnted by `sum[i]` for sum upto i-th index) upto two indices is the same, the sum of the elements lying in between those indices is zero.

`sum[i]` is prefix sum till i-th element

if `sum[j] − sum[i - 1] = k`, then update count.

Thus, storing prefix sum in hashmap, if (sum - k) found, then it means, we found a subarray with sum k.

Also, the hashmap keeps the count for the frequencies of the prefix sum (`sum i, No. of occurences of sum i`), so that it could add together to the total count of the subarray with sum k.

Note: a tricky part is to initialize the hashmap with `map.put(0, 1);`

Since actually the `sum` as hashmap key stored is `sum[0, j]`

and `sum[i, j] = sum[0, j] - sum[0, i - 1]`, therefore if the `sum[0, j]` itself is k, then we are checking if the map contains `0`

as key, so we have `map.put(0, 1);` to make sure the `count` will add one when it find `sum - k == 0`

Some explanation from discussion @y495711146:

``````/*
1. Hashmap<sum[0,i - 1], frequency>
2. sum[i, j] = sum[0, j] - sum[0, i - 1]    --> sum[0, i - 1] = sum[0, j] - sum[i, j]
k           sum      hashmap-key     -->  hashmap-key  =  sum - k
3. now, we have k and sum.
As long as we can find a sum[0, i - 1], we then get a valid subarray
which is as long as we have the hashmap-key,  we then get a valid subarray
4. Why don't map.put(sum[0, i - 1], 1) every time ?
if all numbers are positive, this is fine
if there exists negative number, there could be preSum frequency > 1
*/``````

https://leetcode.com/problems/subarray-sum-equals-k/discuss/102106/Java-Solution-PreSum-%2B-HashMap

Another way (straight-forward, preferred) of implementing it is just do a check outside of the hashmap containsKey(),

``````if (sum == k) {
count++;
}``````

in this way, we don't need to initialize hashmap with (0, 1).

## Solution

Cumulative sum - O(n^2) time, O(1) space (218 ms)

``````public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum=0;
for (int end = start; end < nums.length; end++) {
sum+=nums[end];
if (sum == k)
count++;
}
}
return count;
}
}``````

Prefix Sum + Hash Table - O(n) time, O(n) space (37ms beats 40.49%)

``````class Solution {
public int subarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) return 0;
int sum = 0;
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k)) {
count += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;

}
}``````

Another implementation - Prefix Sum + Hash Table - O(n) time, O(n)

``````class Solution {
public int subarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) return 0;
int sum = 0;
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == k) {
count++;
}
if (map.containsKey(sum - k)) {
count += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;

}
}``````

Last updated