Problem: 560. 和为 K 的子数组
难点
- 怎么通过前缀和找到和为k的子数组
如官方题解所言,[j···i]的子数组=k可转化为pre[i]-pre[j-1]==k
要找到前缀和找到和为k的子数组个数就是“找到当前前缀和pre[i]-之前求得的前缀和=k”的总情况。我们通过哈希表记录每个前缀和(的值)出现的次数(比如下标0到2的和是1,那么mp[1]++,下标3到6的和是1,mp[1]++),就能在O(1)的时间求出“之前求出的前缀和”有多少种子数组。
在for循环中pre[i]可以有pre[i-1]得到——>简化为单个变量,k又是定值,每次都访问mp[pre-k]若存在则能说明[0···i]的子数组能满足“pre[i] - 之前求得的前缀和 = k”
- 为什么是count += hmap[pre-k];而不是count++
count++只表明存在某一个子数组满足,而没有考虑到之前可能已经存在多个位置的前缀和等于 pre - k,故需要累加
Code
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
//不能滑动窗口——k可负
unordered_map<int,int> hmap;
hmap[0] = 1;
int count=0,pre=0;
for(int& x:nums){
pre += x;//求前缀和pre[i]
//如果pre[i] - 之前求得的前缀和 = k
if(hmap.find(pre - k)!=hmap.end()){
//+=而不是++是因为之前可能有多种前缀和都满足
count += hmap[pre-k];
}
hmap[pre]++;//哈希表记录前缀和pre[i]
}
return count;
}
};
标签:pre,count,前缀,560,hmap,++,数组,Leetcode
From: https://www.cnblogs.com/neromegumi/p/18033079