Subarray Sum Equals K

This article focuses on an efficient solution of a popular question, 'Subarray Sum Equals K'.

Leetcode Problem : 560

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

We have to find the total number of subarrays whose total element sum is equal to a given integer k.

Since value of k can be negative also, sliding window approach is not possible.

The idea is to keep on taking cumulative sum of the array and count these cumulative sum values by using an unordered map.

If the sum becomes k, that means all elements up till here make a valid subarray and so we increment our result by one.

Otherwise, if our current cumulative sum is not equal to k, that means somewhere in the array, we need value current cumulative sum - k. Since we store cumulative sum at every step in a map, we could check in the map if we had encountered this value. If yes, that means a valid sub array is possible. Hence we increment our result by the frequency of this value in the map.

Why if we find current cumulative sum - k in our map, a valid subarray is possible ?

Lets understand this by taking a simple example :

Array : {9, 4, 20, 3, 10, 5}
k = 33
map = empty

For i=1, sum = 9

Array : {9, 4, 20, 3, 10, 5}
Subarray = {9} 
sum (9) is not equal to 33 and map is empty.
map = {9}

For i=2, sum = 9 + 4 = 13

Array : {9, 4, 20, 3, 10, 5}
Subarray = {9, 4}
sum (13) is not equal to 33 and sum - k (13-33) = -20 is not present in map.
map = {9, 13}

For i=3, sum = 13 + 20 = 33

Array : {9, 4, 20, 3, 10, 5}
Subarray = {9, 4 , 20}
sum (33) is equal to 33 hence this is a valid subarray! Update result
map = {9, 13, 33}

For i=4, sum = 33 + 3 = 36

Array : {9, 4, 20, 3, 10, 5}
Subarray = {9, 4, 20, 3}
sum (36) is not equal to 33 and sum - k (36-33) = 3 is not present in map.
map = {9, 13, 33, 36}

For i=5, sum = 36 + 10 = 46

Array : {9, 4, 20, 3, 10, 5}
Subarray = {9, 4, 20, 3, 10}
sum (46) is not equal to 33. 

But sum - k (46-33) = 13 is present in map because of the first two elements. 
That means if we remove {9,4} from our current sub array, we get a valid sub array {20, 3, 10} as 20 + 3 + 10 = 33.

Update your result!

map = {9, 13, 33, 36, 46}

For i=6, sum = 46 + 5 = 51

Array : {9, 4, 20, 3, 10, 5}
Subarray = {9, 4, 20, 3, 10, 5}
sum (51) is not equal to 33 and sum - k (51-33) = 18 is not present in map.
map = {9, 13, 33, 36, 46, 18}

Thus, for this example, number of valid subarrays = 2.

Now lets implement our approach!

int subarraySum(vector<int>& nums, int k) {

        unordered_map<int,int> umap;
        int count=0;
        int sum=0;
        for(int i=0;i<nums.size();i++){

            sum+=nums[i];
            if(sum==k)
                count++;
            if(umap.find(sum-k) !=umap.end()){
                count+= umap[sum-k];
            }
            umap[sum]++;
        }
        return count;

    }