和为K的子数组

🟡 Medium · 🏷️ 数组、哈希表、前缀和 · LeetCode#560

📖 题目

统计数组里和为 k 的连续子数组个数。

输入	输出	说明
nums=[1,2,3], k=3	2	[1,2] 和 [3]

💡 思路

数组含负数，滑动窗口的"和越扩越大"这个单调性不成立了，用不了。

换个角度：子数组 [i+1..j] 的和可以写成前缀和之差 prefix[j] - prefix[i]，要找的是有多少对 (i, j) 满足 prefix[j] - prefix[i] = k。变形一下：prefix[i] = prefix[j] - k——遍历到位置 j 时，问题就变成"之前出现过多少次 prefix[j] - k 这个前缀和"。这跟两数之和找 target - num 是不是出现过是同一个套路，只是这里哈希表存的是"出现次数"而不是"下标"。

一个容易漏掉的初始化：{0: 1}，代表"空前缀"的和是 0，出现过 1 次——不加这个，从头开始且刚好等于 k 的子数组会被漏掉（比如 nums=[3], k=3，前缀和是3，要查 3-3=0 有没有出现过）。

还要注意顺序：先查找、后记录——查找的是"之前"的前缀和，不能把当前这个也算进去。

💻 代码

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        d = {0: 1}   # 前缀和 → 出现次数，空前缀和为0，先记一次
        prefix = 0
        count = 0
        for n in nums:
            prefix += n
            count += d.get(prefix - k, 0)       # 先查：之前有几个前缀和 = 当前 - k
            d[prefix] = d.get(prefix, 0) + 1     # 后记：当前前缀和出现次数+1
        return count

时间复杂度 O(n)，空间复杂度 O(n)，哈希表最多存 n 个不同的前缀和。

🔀 跟区域和检索对比

	区域和检索	这题
已知	位置 left, right	目标和 k
求	区间和是多少	有多少个子数组满足条件
用法	正向：知道位置求和	反向：知道和找位置数量