数据结构与算法 / 系统课时

用前缀计数解决子数组问题

用前缀计数解决子数组问题

很多子数组题表面上要求枚举左右端点,真正可利用的是“区间结果等于两个前缀状态之差”。本节用前缀和配合哈希计数,把寻找目标子数组从平方级枚举降为一次线性扫描,并处理负数与重复前缀。

学习目标

  • 把连续子数组条件改写成两个前缀状态之间的关系
  • 用哈希表统计历史前缀状态出现次数,而不是只记录是否出现
  • 正确处理初始前缀、重复状态以及包含负数的数组

把子数组改写成前缀状态差

设 prefix[t] 表示前 t 个元素之和,那么下标区间 [l, r] 的元素和等于 prefix[r + 1] - prefix[l]。因此,要寻找和等于 k 的子数组,在扫描到当前前缀和 p 时,只需要知道历史上有多少个前缀和等于 p - k。

这一步把“选择两个端点”改写成了“查询一个历史状态”。如果 p - k 曾出现三次,就意味着以当前位置结尾的合法子数组有三个,而不是只有一个,所以哈希表必须保存出现次数。

前缀状态差与哈希计数关系

哈希表开始时要放入 0: 1。它表示在读取任何元素之前,前缀和 0 已经出现一次,这样从数组下标 0 开始、元素和恰好等于 k 的子数组也能被统一统计。

扫描时先查询再记录

扫描每个元素时,顺序是:先更新当前前缀和,再查询 prefix - k 的历史次数,最后把当前前缀和写入哈希表。尤其当 k = 0 时,如果先记录当前状态再查询,就会把当前前缀和与自己配对,错误地统计一个空子数组。

下面的完整程序实现 LeetCode 560 类问题,并额外用一个目标和为 0 的例子验证重复前缀计数。

python
from collections import defaultdict
from typing import List


def subarray_sum(nums: List[int], k: int) -> int:
    count = defaultdict(int)
    count[0] = 1  # 空前缀,使从下标 0 开始的合法区间也能被统计

    prefix = 0
    answer = 0

    for value in nums:
        prefix += value
        # 这里只查询已经出现过的前缀,避免把当前位置与自身配对
        answer += count[prefix - k]
        count[prefix] += 1

    return answer


if __name__ == "__main__":
    print(subarray_sum([1, 1, 1], 2))
    print(subarray_sum([1, -1, 0], 0))

预期输出

text
2
3

第一个数组有两个和为 2 的连续子数组;第二个数组存在重复前缀和,因此同一个当前状态可能一次匹配多个历史位置。

为什么不能直接换成滑动窗口

滑动窗口通常依赖某种单调性:窗口扩大后结果只朝一个方向变化,缩小时朝另一个方向变化。数组允许负数时,这个条件会失效。例如加入一个负数可能让窗口和下降,此时无法仅根据当前和决定移动左端还是右端。

前缀计数不要求元素为正。它只利用等式 当前前缀 - 历史前缀 = 目标值,因此正数、负数和 0 都能统一处理。若题目明确限制为非负数组,并且只要求满足某种单调区间条件,滑动窗口才可能是更自然的方案。

记住三个边界

首先,初始化 count[0] = 1,否则会漏掉从数组开头形成的合法子数组。其次,哈希值保存的是出现次数而不是布尔值,因为不同起点可以共享同一个前缀状态。最后,在 Java、C++ 等固定宽度整数语言中,如果数组长度和值域较大,前缀和应使用足够宽的整数类型以避免溢出。

这类题真正需要识别的不是“前缀和”三个字,而是条件能否写成“当前累计状态减去某个历史累计状态”。一旦能这样改写,哈希计数通常就能把双端点枚举压缩成一次线性扫描。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用前缀计数解决子数组问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通