0560. 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

Analysis

We can reduce this to one for-loop to solve this problem. At any point, if we know how many subarrays in front of the current processing point have a sum equal to curr_sum - k, then we can solve this problem in one loop. In other words: curr_sum - x = k, where x is our target complement sum.

So we create a map for that, and keep a record of all the previous sums and their frequency.

• Time: $O(n)$
• Space: $O(n)$, there could be at most n different sums

Code

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = (int)nums.size();
        // key: sum from 0 to i, value: # of this sum occurred
        unordered_map<int, int> m;
        int res = 0;
        int curr_sum = 0;
        m[0] = 1;
        for (int i = 0; i < n; ++i) {
            curr_sum += nums[i];
            res += m[curr_sum - k];
            m[curr_sum]++;
        }
        return res;
    }
};