系列导航：LeetCode Hot100 刷题导航（系列导航） · 上一篇：Hot100 238 | 除自身以外数组的乘积：前缀积和后缀积 · 下一篇：Hot100 73 | 矩阵置零：标记法与原地优化

这一题是前缀和和哈希表结合得非常漂亮的一题。你如果把它真正看懂了，以后很多“某一段区间和满足条件”的题，都会一下子清楚很多。

专栏导读

这题特别适合帮你训练一种很重要的转换能力：

  • 不要直接盯着“子数组和”本身
  • 而要把它改写成两个前缀和之间的关系

一旦这步转化成立，后面就会自然出现：

  • 哈希表记录历史前缀和
  • 一边遍历一边查答案

这篇会重点讲清楚下面几件事：

  1. 子数组和为什么能写成两个前缀和的差
  2. 为什么这题不是滑动窗口题
  3. prefix、freq、count 分别代表什么
  4. 为什么 freq = {0: 1} 一定要先写
  5. 为什么更新字典的顺序不能反

1. 题目到底在说什么

题目给你：

  • 一个整数数组 nums
  • 一个整数 k

你要统计：

  • 有多少个连续子数组
  • 它们的和刚好等于 k

例如：

1
nums = [1,1,1], k = 2

答案是：

1
2

因为有两个连续子数组：

  • 第 0 到 1 位的 [1,1]
  • 第 1 到 2 位的 [1,1]

它们的和都等于 2。

2. 这题最容易误解的地方

这题有两个常见误区。

2.1 这是子数组，不是子序列

题目找的是：

  • 连续的一段

不是从数组里随便挑几个数。

2.2 这题不能直接用滑动窗口模板

很多新手做前缀和题前，会下意识先想滑动窗口。

但这题数组里可能有负数，所以：

  • 窗口扩大以后，和不一定变大
  • 窗口缩小以后，和也不一定变小

这就导致普通滑动窗口没有单调性，不能稳用。

所以这题真正该想的是：

  • 前缀和

3. 先把题目翻译成人话

如果把这题翻译成最直白的话，其实就是：

  • 对每一个结尾位置 r
  • 去问：有没有某个更早的位置 l-1
  • 使得从 l 到 r 这一段的和刚好等于 k

也就是说，这题的关键不是“暴力找所有区间”，而是：

  • 走到当前位置时，快速知道之前有没有合适的前缀和

4. 为什么前缀和会出现

假设我们定义：

  • prefix[i] 表示从开头到位置 i 的和

那么区间 [l, r] 的和就是：

1
prefix[r] - prefix[l-1]

如果这段区间和等于 k，那就说明：

1
prefix[r] - prefix[l-1] = k

移项一下：

1
prefix[l-1] = prefix[r] - k

这句就是整道题的核心转化。

它的人话意思是：

  • 当我走到当前位置，当前前缀和是 prefix[r]
  • 那我只要看看以前有没有出现过值等于 prefix[r] - k 的前缀和
  • 如果有，就说明存在一个以当前位置结尾、和为 k 的子数组

5. 最直观的方法：暴力枚举区间

5.1 为什么先讲暴力法

虽然这题真正推荐的是前缀和 + 哈希表，但对刷题新手来说，最稳的顺序还是：

  1. 先接受一个最直观的解法
  2. 再思考怎么优化

所以最直接的方法就是：

  • 枚举所有起点 i
  • 枚举所有终点 j
  • 算出区间和
  • 看是否等于 k

5.2 Python Tutor 版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def subarray_sum(nums, k):
    count = 0

    for i in range(len(nums)):
        total = 0

        for j in range(i, len(nums)):
            total += nums[j]
            if total == k:
                count += 1

    return count

print(subarray_sum([1,1,1], 2))

5.3 这个方法的问题在哪

它当然正确，但会重复计算很多区间和。

尤其是：

  • 每个结尾位置，都会被不同起点反复算很多次

所以这题真正要学的是：

  • 能不能把“历史信息”存起来，避免反复重算

6. 标准做法：前缀和 + 哈希表

6.1 核心想法

我们一边遍历数组，一边维护当前前缀和 prefix。

走到某个数时，我们做两件事：

  1. 先看以前有没有前缀和等于 prefix - k
  2. 再把当前前缀和记进哈希表里

这样每个位置都可以很快地知道：

  • 以当前位置为结尾，有多少个区间和等于 k

7. Python Tutor 版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def subarray_sum(nums, k):
    count = 0
    prefix = 0
    freq = {0: 1}

    for num in nums:
        prefix += num
        count += freq.get(prefix - k, 0)
        freq[prefix] = freq.get(prefix, 0) + 1

    return count

print(subarray_sum([1,1,1], 2))

8. LeetCode 可提交版代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def subarraySum(self, nums, k):
        count = 0
        prefix = 0
        freq = {0: 1}

        for num in nums:
            prefix += num
            count += freq.get(prefix - k, 0)
            freq[prefix] = freq.get(prefix, 0) + 1

        return count

9. 每一行代码在做什么

先看初始化：

1
2
3
count = 0
prefix = 0
freq = {0: 1}

这里三个变量都非常关键：

  • count：答案，表示目前找到多少个和为 k 的连续子数组
  • prefix：当前前缀和
  • freq：某个前缀和以前出现过多少次

9.1 为什么 freq = {0: 1} 这么重要

这是整题最容易漏掉、也最值得你记住的一句。

它表示：

  • 在正式遍历数组之前
  • “前缀和为 0” 这个状态已经出现过 1 次

为什么要这么设？

因为这能帮助我们处理：

  • 从下标 0 开始的区间

例如：

1
nums = [2, ...], k = 2

当你走到第一个元素时：

  • 当前前缀和就是 2
  • 你需要查 2 - 2 = 0

如果你没有提前放入 freq[0] = 1，这个从开头开始的合法区间就会漏掉。

9.2 遍历时先更新前缀和

1
prefix += num

这表示：

  • 当前走到这个元素后
  • 从开头到这里的总和更新了

9.3 最关键的一句：查 prefix - k

1
count += freq.get(prefix - k, 0)

这句一定要彻底理解。

它的意思是：

  • 当前前缀和是 prefix
  • 如果之前存在某个前缀和等于 prefix - k
  • 那从那个前缀和后面开始，到当前位置结束，这一段区间和就等于 k

为什么是加上“出现次数”？

因为：

  • 同一个前缀和值可能以前出现过不止一次
  • 那就说明有不止一个起点，都能和当前位置组成合法区间

所以不是只加 1，而是加上这个前缀和出现过多少次。

9.4 最后再把当前前缀和记进去

1
freq[prefix] = freq.get(prefix, 0) + 1

这表示：

  • 当前位置的前缀和，以后也可以给后面的元素使用了

这里顺序为什么不能反？

因为你必须先用“之前出现过的前缀和”帮当前点找答案，再把当前前缀和放进去。

如果你先放进去，就会把当前点错误地提前参与匹配，导致逻辑不对。

10. 用经典示例一步一步模拟

示例：

1
nums = [1,1,1], k = 2

开始时：

  • prefix = 0
  • count = 0
  • freq = {0: 1}

走到第一个 1

先更新前缀和：

  • prefix = 1

现在去查：

  • prefix - k = 1 - 2 = -1

哈希表里没有 -1，所以：

  • count 还是 0

然后把 1 记进去：

1
freq = {0: 1, 1: 1}

走到第二个 1

更新前缀和：

  • prefix = 2

现在去查：

  • prefix - k = 2 - 2 = 0

发现：

  • freq[0] = 1

说明之前有 1 个前缀和能和当前点配成区间和为 2。

于是：

  • count = 1

再把当前前缀和 2 记进去：

1
freq = {0: 1, 1: 1, 2: 1}

走到第三个 1

更新前缀和：

  • prefix = 3

现在去查：

  • prefix - k = 3 - 2 = 1

发现：

  • freq[1] = 1

说明又找到一个合法区间。

于是：

  • count = 2

最终答案就是：

1
2

11. 为什么这题和两数之和很像

你如果回头看第一题 两数之和，会发现味道其实很像：

  • 当前值出来之后
  • 不是回头暴力找
  • 而是去查“我需要的那个东西之前有没有出现过”

在 两数之和 里，查的是：

  • 补数

在这题里，查的是：

  • prefix - k

所以这题本质上也是一种：

  • 一边遍历
  • 一边查哈希表

12. 这题顺手学到的 Python 语法

12.1 dict.get(key, 0)

1
freq.get(prefix - k, 0)

表示如果字典里没有这个键，就默认当成 0。

12.2 freq[prefix] = freq.get(prefix, 0) + 1

表示给当前前缀和出现次数加 1。

12.3 一边遍历一边统计

这是哈希表题里非常常见的一种写法。

13. 这题最容易犯的错

13.1 把子数组和子序列混掉

这题找的是连续区间。

13.2 忘了初始化 freq = {0: 1}

这样会漏掉从下标 0 开始的合法区间。

13.3 更新 freq[prefix] 的顺序写反

一定是：

  1. 先用历史前缀和找答案
  2. 再把当前前缀和放进去

13.4 只理解公式，不理解“出现次数”

如果某个前缀和以前出现过多次，那说明对应的合法区间也会有多个。

14. 一句话复盘

这题的本质是：走到当前位置时，去看之前有多少个前缀和刚好等于 当前前缀和 - k。

15. 下一步怎么学

下一题 73. 矩阵置零 会从一维数组切到二维矩阵，重点会变成“先标记，再统一修改”。