560. 和为 K 的子数组
3 min
题目
解法：前缀和哈希
思路
使用前缀和与哈希表记录历史前缀和出现次数。遍历数组时计算当前前缀和，若存在前缀和等于当前值减k，则累加对应次数。
正确性基于数学恒等式：子数组[i,j]的和等于前缀和pre[j]-pre[i-1]=k，即pre[i-1]=pre[j]-k。哈希表保存了所有历史前缀和的出现频次，确保不会遗漏任何可行解。
- Step 1: 初始化哈希表mp，记录前缀和0出现1次（空数组基准）
- Step 2: 遍历数组，累加当前元素到前缀和pre
- Step 3: 若pre-k存在于mp中，累加对应频次到结果count
- Step 4: 更新当前pre在mp中的频次
复杂度
- 时间复杂度: ，遍历数组一次，哈希表操作均摊
- 空间复杂度: ，哈希表最多存储个不同前缀和
代码
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
//注意不能使用滑动窗口，因为有负数
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0;
int pre = 0;
for (auto& x : nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;
}
return count;
}
};