LC560　和为 K 的子数组¶

中等通过率 46.9%python3核心代码模式子串样例通过牛客 AC数组哈希表前缀和

一句话

前缀和把区间和变成差，再用哈希表数「有多少个合适的左端」。

解题思路¶

这题考什么¶

数组含负数，所以不能用滑动窗口：窗口右扩时和不再单调增，「和太大就收左端」这条规则失效，双指针的单调性根本不成立。这是本题的分水岭。

正确的模型是前缀和（prefix sum，见前缀和与差分）。记 S[i] = nums[0] + … + nums[i-1]，S[0] = 0，则子数组 nums[l .. r] 的和是 S[r+1] - S[l]。于是「和为 k 的子数组个数」等价于

有多少对下标 (i, j)，i < j，满足 S[j] - S[i] == k

把它改写成 S[i] == S[j] - k：固定右端 j，要数的就是在 j 左边出现过多少次值为 S[j] - k 的前缀和。这正好是哈希表擅长的计数查询，一遍扫描即可。

pre = {0: 1}                    前缀和的值 -> 出现次数
cur = 0
对每个元素 x：
    cur += x                    此刻 cur 就是 S[j]
    ans += pre.get(cur - k, 0)  先查：表里全是 j 左边的前缀和
    pre[cur] += 1               后存：把 S[j] 自己留给右边的元素

pre[0] = 1 这个初值不能省：S[0] = 0 是一个真实存在的前缀和，代表「空前缀」这个左端点。所有从下标 0 开始、和恰为 k 的子数组，都要靠它来计数。少了它，nums = [1, 1, 1]、k = 2 会漏掉 nums[0..1]，答案从 2 变成 1。

先查后存的顺序保证 i < j 严格成立（长度为 0 的子数组和为 0， k = 0 时不该被计入）。

数据规模与复杂度¶

1 <= n <= 2e4，-1000 <= nums[i] <= 1000，-1e7 <= k <= 1e7。前缀和的绝对值上界 2e4 * 1000 = 2e7，Python 整数不会溢出。时间 O(n)：一遍扫描，每步两次字典操作；空间 O(n)—— 最坏所有前缀和互不相同，表里存 n + 1 个键。枚举左右端点再求和是 O(n^2) 甚至 O(n^3)，2e4 的平方是 4e8，Python 下超时。

坑在哪¶

有负数，滑动窗口不适用。前缀和不再单调，「和超了就收缩左端」的推理不成立——收缩之后和可能反而变大。看到「子数组求和计数」先确认元素是否非负，这是选滑动窗口还是前缀和的判据。
pre[0] = 1 的初值是整题最容易漏的一条，理由如上： S[0] = 0 对应「从数组开头起」的那个左端点，它必须先在表里。
顺序必须是先查后存。若先把 cur 存进表再查 cur - k， k = 0 时当前这个前缀和会查到刚写进去的自己，等于把长度为 0 的空子数组计入答案，每个位置都多算一次。
表里存的是次数不是位置。同一个前缀和值可能出现多次，每一次都对应一个合法左端；写成「值 -> 下标」只会记住一个，答案会算小。 nums = [1, -1, 1, -1]、k = 0 的答案是 4，正是靠计数才数得出来。
累加的是 pre.get(cur - k, 0) 而不是 1。命中意味着左边有若干个可用左端，有几个就加几个，写成 if cur - k in pre: ans += 1 会把重复出现的前缀和只算一次。
严格比对：答案是一个整数，没有多解。

样例复核¶

nums = [1, 1, 1]，k = 2，期望 2。

初始 pre = {0: 1}，cur = 0，ans = 0
x=1  cur=1  查 pre[1-2] = pre[-1] 不存在 -> ans=0   pre = {0:1, 1:1}
x=1  cur=2  查 pre[2-2] = pre[0] = 1     -> ans=1   pre = {0:1, 1:1, 2:1}
            （命中的正是初值那条：对应子数组 nums[0..1] = [1,1]）
x=1  cur=3  查 pre[3-2] = pre[1] = 1     -> ans=2   pre 再加 {3:1}
            （对应子数组 nums[1..2] = [1,1]）

答案 2，与样例一致。去掉 pre[0] = 1，第二步就查不到，答案会错成 1。

参考实现¶

solutions/leetcode/LC560/sol.py
from typing import List, Optional


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 前缀和的值 -> 它出现过多少次。存次数而不是下标：同一个前缀和值
        # 每出现一次就是一个可用的左端点，都要计入
        # 初值 {0: 1} 代表「空前缀」S[0] = 0，它是所有从下标 0 开始的子数组的左端；
        # 漏了这一条，[1,1,1] 与 k=2 会少数一个，答案从 2 变成 1
        pre = {0: 1}
        cur = 0             # 扫到当前位置为止的前缀和，即 S[j]
        ans = 0
        for x in nums:
            cur += x
            # 子数组和 = S[j] - S[i]，要它等于 k 就是要 S[i] == cur - k。
            # 先查：表里装的全是当前位置**左边**的前缀和，于是 i < j 自动成立，
            # 长度为 0 的空子数组不会在 k == 0 时被误计
            ans += pre.get(cur - k, 0)
            # 后存：把 S[j] 自己留给右边的元素当左端点用。同值累加次数，不覆盖
            pre[cur] = pre.get(cur, 0) + 1
        return ans

LC560 和为 K 的子数组¶