560. Subarray Sum Equals K

[fockspaces]

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

[fockspaces]

要找有多少區間段總和為k，可以先將累計數組求出 當 sum[j] - sum[i] 為 k 時，表示 i ~ j 這段總和為 k 先維護每段總和數組值的出現次數，接著更新 ans 即可

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> map; map[0] = 1;
        int cur = 0, ans = 0;
        for(int num : nums) {
            cur += num;
            ans += map[cur - k]; 
            map[cur]++;
        }
        return ans;
    }
};