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[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