leetcode
560.和为K的子数组
暴力超时
class Solution {
public:
int subarraySum(std::vector<int>& nums, int k) {
int cnt = 0;
for (int end = 0; end < nums.size(); end++){
int sum = 0;
// 注意此处必须！！反向遍历
for (int start = end; start >= 0; start--){
sum += nums[start];
if (sum == k) cnt++;
}
}
return cnt;
}
};
为什么反向遍历
前缀和 哈希表
class Solution {
public:
int subarraySum(std::vector<int>& nums, int k) {
std::unordered_map<int, int> umap;
umap[0] = 1;
int cnt = 0, presum = 0;
for (int i:nums){
presum += i;
// 找 pre[j-1]==pre[i]-k
if (umap.find(presum - k) != umap.end()) cnt += umap[presum - k];
umap[presum]++;
}
return cnt;
}
};