C++速通LeetCode中等第7题-和为K的子数组（巧用前缀和）
巧用哈希表与前缀和，前缀和差为k的两个序号之间的数组就是满足条件的子数组，用哈希表来存放每个序号的前缀和。
前缀和就是头元素到当前序号子数组元素的和
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto& x:nums) {
pre += x;
if (mp.count(pre - k)) {//看有没有前缀和差为目标k的两个序号
count += mp[pre - k];//有的话答案加上满足的前序数量
}
mp[pre]++;//记录每一个序号的前缀和，前缀和相等的话，map->second计数会加一
}
return count;
}
};
原文地址：https://blog.csdn.net/weixin_47768406/article/details/142353493
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！