【做一道算一道】和为 K 的子数组

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

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

示例 1：

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

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

提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

思路

看到想到是滑动窗口，调了力扣结果和本地调的对不上，看题解，发现说有负值，那滑动就不行。
官解是前缀和，记一下。
其中关键代码是：

count += mp[pre - k]; // 如果存在前缀和为pre - k，更新count

表示如果mp中存在pre - k，说明存在一个前缀和为pre - k，那么从这个前缀和的末尾到当前索引的子数组和为k。即从pre - k前缀和的末尾到当前索引位置的子数组满足条件，可被记录。
因此，将count增加mp[pre - k]（该前缀和出现的次数，每个对应一种满足的情况）。

代码

滑动窗口（仅适合全为正）：
奇怪的点，全为正的时候，本地调是正确的，力扣上结果就不对，不知道哪儿有问题。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int sum=0;int l=0,r=0;int cnt=0;sort(nums.begin(),nums.end());if(k<nums[0])return cnt;while(r<nums.size()){sum+=nums[r++];while(sum>=k){if(sum==k){cnt++;}sum-=nums[l++];  }}return cnt;}
};

前缀和：

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> mp;mp[0] = 1; // 初始化前缀和为0的出现次数为1int count = 0, pre = 0;for (auto x : nums) {pre += x; // 更新前缀和count += mp[pre - k]; // 如果存在前缀和为pre - k，更新countmp[pre]++; // 更新当前前缀和的出现次数}return count;}
};

官解当中多一个判定：

if (mp.find(pre - k) != mp.end())

可省略，因为即使 mp[pre - k] 之前没有出现过，其值也是0，不会对 count 产生影响。