前缀和

01 / 共享的机制

前置花一次 O(N) 构建累积表 —— 之后的每次区间查询就退化成一次常数级减法。 把这个套路反过来用,就能在区间更新上同样廉价。

01 / 一句话本质
只扫一遍维护运行前缀和; 每一步以此处结尾的合法子数组数,等于哈希表里已经登记的 prefix − k 出现次数。
题目统计和等于 k 的子数组个数输入[1, 2, 3, -1, 2, 3]k5
prefix0
arr
1
0
2
1
3
2
-1
3
2
4
3
5
map
0·1
从左到右扫描 arr,目标 k = 5。哈希表预置 { 0: 1 } —— 这一项专门处理从下标 0 开始的子数组。
步
0 / 19
阶段
初始
prefix
0
查询值
·
命中
·
计数
0
0 / 19

02 / 模式骨架

# 遍历 arr,维护哈希表count ← 0prefix ← 0map ← { 0: 1 } # 空前缀的种子for x in arr:prefix ← prefix + x# 查表if (prefix − k) in map:count += map[prefix − k]map[prefix] += 1 # 登记当前前缀,供后续步骤查询

03 / 什么时候用这个模式

"子数组和等于 k 的个数"
最典型的信号。子数组的和就是两个前缀的差,所以每个以 i 结尾的合法子数组都对应一个先前的前缀 prefix[i] − k。查表,不嵌套循环。
"能被 k 整除的子数组"
同样的思路,只是哈希表的键换成 prefix mod k。任何对 k 模意义下可加的量都适用。
"+1 / −1 前缀"
先重新编码原值(例如 0 → −1),让目标性质变成「两个前缀相等」, 就能继续用同一套哈希表计数。
"满足性质 P 的最长 / 最短子数组"
套路一样,但哈希表存的是每个前缀值最早出现的位置,答案是 i − map[prefix − k]。计数变成查下标。

04 / 常见坑

i.
忘了写 { 0: 1 } 种子。
这个种子用来处理从下标 0 开始的子数组 —— 也就是 prefix[i] 本身就等于 k 的情况。少了它,每个自身等于目标的前缀都会被悄悄漏掉。
ii.
先登记前缀再查表。
顺序必须是先查后登。如果先 map[prefix] += 1, 当 k = 0 时长度为 0、和为 0 的「子数组」会把自己也算进去。 查询时哈希表里只能有严格更早位置的前缀。
iii.
把频次写成了 1。
应是 count += map[prefix − k],不是 count += 1。 同一个前缀值可能出现过很多次(尤其有负数或零时),每次都对应一个以 i 结尾的不同子数组。

05 / 去 LeetCode 上练习

四道题,按难度排序。这里有意不放解答。

01Subarray Sum Equals K— LC 560中等→02Subarray Sums Divisible by K— LC 974中等→03Contiguous Array— LC 525中等→04Count Number of Nice Subarrays— LC 1248中等→

— / 什么时候用哪个

一维线性
当对一个固定数组有很多次区间求和查询时使用。
区间和 · 累计 · LC 303
二维网格
用于矩阵上的矩形查询 —— 四个角上做容斥。
矩形区域 · 块和 · LC 304
差分
反过来用:很多次区间更新,最后一次性扫出每个位置的值。
区间加 · 拼车 · 航班预订
哈希映射
统计和等于目标值的子数组数 —— 前缀和 + 已见前缀的哈希表。
和为 K · 整除 K · LC 560