# Subarrays with given sum

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 = -10
Output:
1
Explanation:
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 = 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.

### 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 = 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).