560. 和为 K 的子数组

子数组、子串是连续的；子序列是不连续

</aside>

前缀和用来快速地计算某一段区间的和。

$P[i] = A[0] + A[1] + \cdots + A[i]$ → $\text{sum}(l, r) = P[r] - P[l-1]$

</aside>

对原数组求前缀和后，一个和为 k 的子数组即为一对前缀和的差值为 k 。用哈希表记录每个前缀和出现的次数。特别地，初始时前缀和为 0 需要被额外记录一次。

为什么 cnt[0] = 1; cnt[x] 表示区间和为 x 的数量有多少个，cnt[0] 表示区间和为 0 的数量有 1 个。你可以理解为有一个空的区间，也就是不选

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        cnt[0] = 1;
        int preSum = 0, res = 0;
        for (int x : nums) {
            preSum += x;
            res += cnt[preSum - k];
            cnt[preSum]++;
        }
        return res;
    }
};