Array : Subarray Sum Equals K

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

Example 1:
 
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
 
Input: nums = [1,2,3], k = 3
Output: 2
 
 
Constraints:
 
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

Beautiful solution:https://leetcode.com/problems/subarray-sum-equals-k/solution/

Approach 4: Using Hashmap

Algorithm

The idea behind this approach is as follows: If the cumulative sum(repreesnted by sum[i] for sum upto ith index) upto two indices is the same, the sum of the elements lying in between those indices is zero. Extending the same thought further, if the cumulative sum upto two indices, say i and j is at a difference of k i.e. if sum[i]−sum[j]=k, the sum of elements lying between indices i and j is k.

Based on these thoughts, we make use of a hashmap map which is used to store the cumulative sum upto all the indices possible along with the number of times the same sum occurs.

We store the data in the form: (cumulative_sum[i] ,no. of occurances of cumulative_sum[i]).

We traverse over the array num and keep on finding the cumulative sum. Every time we encounter a new sum, we make a new entry in the hashmap corresponding to that sum. If the same sum occurs again, we increment the count corresponding to that sum in the hashmap. Further, for every sum encountered, we also determine the number of times the sum sum−k has occured already, since it will determine the number of times a subarray with sum k has occured upto the current index. We increment the count by the same amount.

After the complete array has been traversed, the count gives the required result.

The animation below depicts the process.

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Step 8:

Step 9:

To simplify further:

There could be two situations.

In situation 1, the subarray with the target sum starts from the beginning of the array. That means that the current prefix sum is equal to the target sum, and we increase the counter by 1.

Figure 5. Situation 1: The subarray starts from the beginning of the array.

In situation 2, the subarray with the target sum starts somewhere in the middle. That means we should add to the counter the number of times we have seen the prefix sum curr_sum - target so far: count += h[curr_sum - target].

The logic is simple: the current prefix sum is curr_sum, and some elements before the prefix sum was curr_sum - target. All the elements in between sum up to curr_sum - (curr_sum - target) = target.

Figure 6. Situation 2: The subarray starts somewhere in the middle.

Solution :

If the same sum occurs again, we increment the count corresponding to that sum in the hashmap. Further, for every sum encountered, we also determine the number of times the sum sum−k has occured already, since it will determine the number of times a subarray with sum k has occured upto the current index. We increment the count by the same amount.

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hashmap = {}
        cum_sum = 0
        count = 0
       
        # We traverse array & keep on finding the cumulative sum.
        for num in nums:
            cum_sum += num
            
            if cum_sum - k in hashmap:
                count += hashmap[cum_sum - k]
                
            if cum_sum == k:
                count += 1
            
            if cum_sum in h:
                #Same sum is found, increment the count corresponding to that sum in hashmap
                hashmap[cum_sum] += 1
            else:
                #A new sum found, make a new entry                   
                hashmap[cum_sum] = 1
            
                
        return count

**Complexity Analysis**

• Time complexity : O(n). The entire nums array is traversed only once.
• Space complexity : O(n). Hashmap map can contain upto n distinct entries in the worst case.