560. Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to the k.

Example

Example1

Input: nums = [1,1,1] and k = 2
Output: 2
Explanation:
subarray [0,1] and [1,2]

Example2

Input: nums = [2,1,-1,1,2] and k = 3
Output: 4
Explanation:
subarray [0,1], [1,4], [0,3] and [3,4]

class Solution {  
public:  
    int subarraySum(vector<int>& nums, int k) {  
        int count = 0, sum = 0;  
          
        unordered_map<int, int> mp{{0, 1}};  
        for (auto n: nums) {  
            sum += n;  
            count += mp[sum - k];  
            mp[sum]++;  
        }  
          
        return count;  
    }  
};  

Use example2 to explain this code. 

1. mp[0] = 1;

   sum = nums[0] = 2, and k = 3. 

Now count = count + mp[-1] = 0, then set mp[2] = 1.

2. mp[0] = 1, mp[2] = 1;

   sum = 2 + nums[1] = 3, and k = 3. 

Now count = 0 + mp[0] = 1, then set mp[3] = 1.

3. mp[0] = 1, mp[2] = 1, mp[3] = 1;

   sum = 3 + nums[2] = 2.

Now count = 1 + mp[-1] = 1, then set mp[2] = 2.

4. mp[0] = 1, mp[2] = 2, mp[3] = 1;

   sum = 2 + nums[3] = 3.

Now count = 1 + mp[0] = 2, then set mp[3] = 2.

5. mp[0] = 1, mp[2] = 2, mp[3] = 2;

   sum = 3 + nums[4] = 5.

Now count = 2 + mp[2] = 4, then set mp[5] = 1. 

Finally, the answer is 4.