560. 和为 K 的子数组

难度：🟡 Medium | 标签：前缀和、哈希 | 状态：⬜ LeetCode 链接

思路

前缀和 + 哈希。sum[j] - sum[i] = k ⇔ sum[i] = sum[j] - k，遍历 j 时查 sum[j] - k 在前面出现几次。

哈希初始 mp[0] = 1——表示「前缀和本身等于 k」的情况。

⚠️ 数组含负数，不能用滑动窗口。

代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp{{0, 1}};
        int sum = 0, res = 0;
        for (int x : nums) {
            sum += x;
            auto it = mp.find(sum - k);
            if (it != mp.end()) res += it->second;
            mp[sum]++;
        }
        return res;
    }
};

复杂度

• 时间 O(n)，空间 O(n)

易错 / 回顾

• 顺序：先查后插。否则 nums=[0], k=0 会重复计数
• mp[0] = 1 必加
• 含负数 → 不能用滑窗，前缀和 + 哈希是唯一线性解