LC560.和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 10⁴
• -1000 <= nums[i] <= 1000
• -10⁷ <= k <= 10⁷

思路：前缀和 + 哈希表

• 为什么滑动窗口不行？这个题我第一反应就是滑动窗口，但是事实上是不行的。因为随着窗口的收缩，子数组和可能变大可能变小，变化方向不一致。
• 哈希表rec，前缀和summ，rec[summ[i]] = k，表示前缀和中，有k个值为summ[i]的数字。这一点是理解的核心。记录和为k的子数组的计数器是cnt。
• 在逐次遍历的过程中，对于summ[i]而言，如果rec当中出现了summ[i] - k，说明遍历过的数字当中，某个数字summ[j]，可以满足summ[i] - summ[j] == k，也就是nums[j] + ... + nums[i - 1]，该子数组的和就是k。对于之前遍历过的哈希表而言，rec[summ[j]]，值未必是1，也就是上面提到的j，可能存在许多个。因此，cnt += rec[summ[i] - k]。
• 脑子里还是要有图。
• 哈希表：键：前缀和，值：该前缀和出现的次数

代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> summ(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            summ[i] = summ[i - 1] + nums[i - 1];
        }

        unordered_map<int, int> rec;

        int cnt = 0;
        for (int i = 0; i <= n; i++) {
            if (rec.count(summ[i] - k)) {
                cnt += rec[summ[i] - k];
            }
            rec[summ[i]] += 1;
        }

        return cnt;
    }
};