We are given an unsorted array containing positive and negative numbers, we need to find the number of subarrays with the given sum, k. For example,

Input:arr = [2, 4, -5, -5, 6] and k = -10Output:1Explanation:We can see that there is only one subarray (index 2 to 3) whose sum is -10.

## Thought process

If the sum of elements in the range `[0, i]` and `[0, j]` is the same, then we can say that the sum between `[i + 1, j]` will be zero. This statement will be more clear after understanding the below example.

Let’s take arr = [2, 4, 4, -10, 4, 6, 5, 6]. Sum of elements in the range `[0, 2]` = 2 + 4 + 4 = 10

Sum of elements in the range `[0, 5]` = 2 + 4 + 4 + (-10) + 4 + 6 = 10

The above two sums are the same. Here,`i`= 2 and `j` = 5. Let’s check whether the sum in the range `[3, 5]` is 0 or not. Sum of elements in the range `[3, 5]` = -10 + 4 + 6 = 0

Hence, the statement explained above is true.

Read more here: subarray with sum zero

We can extend this idea to this question. The modified statement is as follows if the difference of the sum of elements in the range `[0, j]`and `[0, i]` is `k`, then we can say that the sum between `[i + 1, j]` is k. Mathematically,

If Sum[0, j] - Sum[0, i] = k, where j > i Then, Sum[i + 1, j] = k or Sum[0, j] - k = Sum[0, i]

For each index `j` in the array, if we have seen `Sum[0, j] – k` in the past, then we have found the subarray. But how to achieve this?

Let’s number of elements in an array is `n`. So, we need to maintain sum[0, 0], sum[0, 1], sum[0,2], sum[0, 3] … sum[0, n].

These sums are known as prefix sum. If the same sum occurs many times, we store the frequency of occurrence. We can use a hashmap where the key will denote the sum and value will denote the frequency of occurrence.

Any corner cases? What if k = sum[0, j], where `j` is an index. For this, `sum[0, j] – k` is 0 and we will try to find if we have seen 0 as the sum in the past. To handle this case, we will insert one entry to map as a map[0] = 1.

## Algorithm

1. For each index in the array. 1.1 sum = sum in the range [0, i] 1.2 Check if sum - k is already encountered in the array, i.e have we encountered any array in the past whose the sum is sum - k. 1.3 If yes, add the frequency of sum - k to answer. 2. Finally, put the sum in the map with frequency as 1 if the sum is not seen in the past. 3. If the sum is seen in the past, update frequency as old frequency + 1. 4. Finally, print the answer.

### Show me the implementation

// nums = given array // k = sum int subarraySum(vector<int>& nums, int k) { int ans = 0; // to store the final count int sum = 0; // to store sum // to store prefix sum along with frequency map<int, int> map; map[0] = 1; // for case like k = sum[0, i] for(int i = 0; i < nums.size(); i++) { // calculating sum in the range[0, i] sum += nums[i]; // if sum - k is alread seen if(map.find(sum - k) != map.end()) ans += map[sum - k]; // add frequency // if sum is not seen in the past if(map.find(sum) == map.end()) map[sum] = 1; else map[sum] = map[sum] + 1; } return and; }

Time Complexity of the implementation is `O(n)` along with the space Complexity of `O(n)`.

This article is contributed by Mukul Vashishtha