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