LC560.和为k的子数组

原题链接

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

• 示例 1：

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

• 示例 2：

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

• 提示：

• 
• 

• 

  思路：前缀和 + 哈希表

• 为什么滑动窗口不行？这个题我第一反应就是滑动窗口，但是事实上是不行的。因为随着窗口的收缩，子数组和可能变大可能变小，变化方向不一致。

• 哈希表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;
    }
  };