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 to one forloop to solve this problem. At any point, if we know how many subarrays in front of the current processing point, that the area is equal to curr_sum - k, then we can solve this problem in one loop. Or meaning: 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 sum and their freqency.

• Time: $O(n)$
• Space: $O(n)$ there could have at most n difference sum

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;
    }
};

---

Last update: April 1, 2022