給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，請(qǐng)你統(tǒng)計(jì)并返回 該數(shù)組中和為 k 的子數(shù)組的個(gè)數(shù) 。

子數(shù)組是數(shù)組中元素的連續(xù)非空序列。

示例 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

思路

看到想到是滑動(dòng)窗口，調(diào)了力扣結(jié)果和本地調(diào)的對(duì)不上，看題解，發(fā)現(xiàn)說(shuō)有負(fù)值，那滑動(dòng)就不行。
官解是前綴和，記一下。
其中關(guān)鍵代碼是：

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

表示如果mp中存在pre - k，說(shuō)明存在一個(gè)前綴和為pre - k，那么從這個(gè)前綴和的末尾到當(dāng)前索引的子數(shù)組和為k。即從pre - k前綴和的末尾到當(dāng)前索引位置的子數(shù)組滿足條件，可被記錄。
因此，將count增加mp[pre - k]（該前綴和出現(xiàn)的次數(shù)，每個(gè)對(duì)應(yīng)一種滿足的情況）。

代碼

滑動(dòng)窗口（僅適合全為正）：
奇怪的點(diǎn)，全為正的時(shí)候，本地調(diào)是正確的，力扣上結(jié)果就不對(duì)，不知道哪兒有問(wèn)題。

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的出現(xiàn)次數(shù)為1int count = 0, pre = 0;for (auto x : nums) {pre += x; // 更新前綴和count += mp[pre - k]; // 如果存在前綴和為pre - k，更新countmp[pre]++; // 更新當(dāng)前前綴和的出現(xiàn)次數(shù)}return count;}
};

官解當(dāng)中多一個(gè)判定：

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

可省略，因?yàn)榧词?mp[pre - k] 之前沒(méi)有出現(xiàn)過(guò)，其值也是0，不會(huì)對(duì) count 產(chǎn)生影響。