题目链接:力扣
注意:此题不能使用滑动窗口,因为数组中可能会出现负数。也就是说右指针向后移1位不能保证区间会增大,左指针向后移1位也不能保证区间和会减小。给定左右指针的位置没有二段性
已知sum[i]是从nums[0~i]的和,sum[i-1]是nums[0~i-1]的和
则有 sum[i] - sum[i-1] = nums[i]
则存在一个j(0<=j<=i) 使得sum[i]-sum[j] = k;
即sum[j] = sum[i]-k; 这个sum[j]的个数就是数组中和为k的连续子数的个数
在本题解中,在循环中完成sum[i]的计算即sum文章来源:https://www.toymoban.com/news/detail-579717.html
这里用map来记录sum-k的个数文章来源地址https://www.toymoban.com/news/detail-579717.html
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
map<int,int> mymap; //key:值 value:出现的次数
mymap[0]=1;
int sum =0, ret =0;
for(int i=0;i<nums.size();i++)
{
//使用map记录出现同样的和的次数, 对每个i计算累计和sum并判断map内是否有sum-k
sum+=nums[i];
if(mymap.find(sum-k)!=mymap.end())
ret += mymap[sum-k];
mymap[sum]++;
}
return ret;
}
};
到了这里,关于和为 K 的子数组——前缀和+哈希的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!