Subarray Sum Equals K - O(N) HashMap cummulative sum

Array     C++     Hash Table     Medium     Prefix Sum    

Problem Statement:

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

A subarray is a contiguous non-empty sequence of elements within an array.

 

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

Solution:

Algorithm:

• Maintain a HashMap of cummulative sum of array using variable curr
• If you see that curr-k is in HashMap, add it to the count of contiguous subarrays
• Add curr to the HashMap.

 
#define ll long long
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n=nums.size(), res=0; ll curr=0;
        unordered_map<ll,int> H;
        H[0] = 1; // At i=-1 we have seen 0
        for (int i=0; i<n; i++)
        {
            curr+=nums[i];
            if (H.count(curr-k)) res+=H[curr-k];
            H[curr]++;
        }
        return res;
    }
};