前缀和算法核心：8类高频题型与面试实战

前缀和这个东西，说穿了就是预处理一个累加数组，把一堆区间求和从 O(n) 变成 O(1)。我经常跟准备面试的朋友说，如果子数组求和、子矩阵求和这类题老是卡壳，八成是还没把前缀和这套思维真正装进脑子。这篇文章我直接把平时刷题、出题时最常用的 8 类高频场景拉出来过一遍，每一类都会讲清楚“为什么能这么做”而不是只贴代码。无论你是刚接触算法的初学者，还是准备跳槽想快速过一遍高频题型的开发者，都可以照着这个体系往下走。

我会尽量用实际推导和踩坑记录来说话，不整虚的。看完之后你会发现，前缀和不只是一个公式，它更是一种“把查询变成记忆”的思维方式。

1. 先从最朴素的问题说起：为什么一段区间的和可以 O(1) 拿到

1.1 暴力的痛：每次查询都重新累加，迟早被面试官灵魂拷问

先看最经典的场景：给你一个数组，反复询问某个区间[l, r]的和是多少。第一次问，你循环一遍，输出累加结果，没问题。第二次问，你又循环一遍，也可能没问题。但如果面试官说“我要查一万次”，每一次都重新从l加到r，总复杂度就是O(n * m)，m 是查询次数，n 是数组长度。遇到大数据量或者线上系统，这个方案基本是废的。

我第一次理解前缀和，靠的是一个特别生活化的类比：想象你在银行有一张流水单，每一笔存钱取钱都记下来。你想知道“3月5日到3月20日我到底净变动了多少钱”，最笨的办法是把这些天的流水全部重算一遍。但如果你每天都记录一个“截至今天的账户余额”，那你只需要用“3月20日的余额”减去“3月4日的余额”，就把中间这段区间的净变动算出来了。所谓前缀和，其实就是这张“截至今天的余额表”。

1.2 前缀和的数学本质：差分与还原的关系

前缀和数组的定义很简单：设原始数组为a，长度是n，我们构造一个pre数组，其中pre[i]表示a[0]到a[i-1]的和，也就是前i个元素的和。这里要注意下标设计，我习惯用“前 i 项和”而不是“到下标 i 的和”，因为这样能减少很多边界失误。

推导公式就是：

pre[0] = 0 pre[i] = pre[i-1] + a[i-1] (i >= 1)

如果要查询a[l]到a[r]的和，不需要循环，直接：

sum(l, r) = pre[r+1] - pre[l]

为什么成立？因为pre[r+1]是前r+1项和，pre[l]是前l项和，两者相减，恰好剩下下标从l到r的部分。这个公式是整个前缀和体系的地基。你后面遇到的二维前缀和、子数组和等于 K、子矩阵最大和，本质上都是这条公式的各种变体。

1.3 这类题统一的长相

我总结过一个规律：只要题目里出现“连续子数组”“连续子序列”“子矩阵”“区间和”这些词，同时还有大量查询或者要求某种最优值，十有八九都能用前缀和来优化。面试里最常考的八类题型，其实就是下面这张表：

后面我就按这张表逐类拆。

2. 第一梯队：区间求和模板，基础但必须秒写

2.1 一维数组区间和检索：高频题的“鼻祖”

题目大概是这样的：给定一个整数数组，要求实现一个函数，能够多次查询某个下标区间内所有元素的和。这类题在面试里属于“热身但能看出基本功”的题目。面试官看重的不是你会不会暴力，而是你能不能想到预处理。

我的标准写法如下：

class PrefixSum: def __init__(self, nums): n = len(nums) self.pre = [0] * (n + 1) for i in range(n): self.pre[i + 1] = self.pre[i] + nums[i] def range_sum(self, l, r): # 返回 [l, r] 的和，注意 r 是闭区间 return self.pre[r + 1] - self.pre[l]

这里的核心点是把pre数组的长度设为n + 1，pre[0] = 0这个哨兵位极其重要。有了它，查询[0, r]的时候直接pre[r+1] - pre[0]，不需要单独讨论边界。我见过很多新手把pre长度设成n，然后查询时对下标各种加一减一，结果越绕越乱。一个经验：让前缀和数组永远比原数组多一位，以 0 开头，这是最省心的写法。

复杂度方面，构造是O(n)，每次查询是O(1)，整体构建空间O(n)。这已经是最优解了，面试官一般不会再追问，除非他把数组改成可以原地更新的场景，那就要上树状数组或者线段树，不属于今天讨论的范畴。

2.2 二维区域和检索：从一维到矩阵的跳跃

二维版本是高频题的常客：给定一个二维矩阵，多次查询某个子矩形区域内所有元素的和。如果每次查询都去双重循环，那复杂度是O(n*m)，查询一多就完蛋。正确做法是把一维前缀和推广成二维前缀和。

二维前缀和的构造思想是一个矩形区域内数字的总和，等于四个区域之间的加减组合。用数学公式说就是，设ps[i][j]表示从左上角(0,0)到(i,j)这个子矩阵的元素总和，那么递推式是：

ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + matrix[i][j]

为什么是减一次ps[i-1][j-1]？因为ps[i-1][j]和ps[i][j-1]相加时，左上角那块ps[i-1][j-1]被算了两次，所以要减掉一次。这个“容斥”思想是二维前缀和最容易记混的地方。

查询子矩阵(r1, c1)到(r2, c2)的和，公式是：

sum = ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1]

实现时我习惯在矩阵外围加一圈 0，也就是ps的大小是(m+1) x (n+1)，这样查询时把行列都加一，完全不用考虑下标会不会越界：

class MatrixSum: def __init__(self, matrix): m, n = len(matrix), len(matrix[0]) self.ps = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m): for j in range(n): self.ps[i + 1][j + 1] = (self.ps[i][j + 1] + self.ps[i + 1][j] - self.ps[i][j] + matrix[i][j]) def submatrix_sum(self, r1, c1, r2, c2): return (self.ps[r2 + 1][c2 + 1] - self.ps[r1][c2 + 1] - self.ps[r2 + 1][c1] + self.ps[r1][c1])

这道题我推荐每个认真准备面试的人都手写三遍以上。倒不是因为它难，而是因为它建立了一种“从一维到二维的平移感”，后面理解行压缩、最大子矩阵和都会顺很多。

2.3 这类题的三个边界细节

第一，从 1 开始还是从 0 开始？我强烈建议你统一使用“从 0 开始的原数组 + 多一位的 pre 数组”这套写法，写多了不容易错。第二，查询区间到底是开区间还是闭区间，一定要跟面试官确认清楚，或者自己固定用闭区间，然后代码里都按闭区间写，避免混乱。第三，如果数组里可能有负数，前缀和依然完全可用，因为累加跟正负无关，只是查询结果可能是负的而已。

3. 第二梯队：子数组计数，前缀和要和哈希表配合

3.1 和为 K 的子数组：经典中的经典

题目是这样的：给定一个整数数组和一个目标值 K，统计有多少个连续子数组的和恰好等于 K。大多数人的第一反应是枚举所有子数组的起点和终点，然后求区间和。这样是O(n^2)起步，如果再用循环求和就是O(n^3)，面试里基本不可能通过。

正确思路是：任意连续子数组[j, i]的和都能写成pre[i+1] - pre[j]。题目要求这个值等于 K，也就是pre[i+1] - pre[j] = K，移项得到：

pre[j] = pre[i+1] - K

也就是说，我们只需要遍历每一个下标i，看历史上有多少个前缀和的值等于pre[i+1] - K，这些数量累加起来，就是答案。怎么快速知道历史上某个前缀和出现多少次？用哈希表，键是前缀和的值，值是出现次数。

def subarray_sum(nums, k): count = 0 pre_sum = 0 mp = {0: 1} for x in nums: pre_sum += x if pre_sum - k in mp: count += mp[pre_sum - k] mp[pre_sum] = mp.get(pre_sum, 0) + 1 return count

这里有个非常重要的细节：为什么哈希表初始化要写成{0: 1}？因为前缀和为 0 的情况在开始之前就存在，表示“空前缀”。如果不初始化，那么当pre_sum恰好等于 K 的时候，你会漏算“从下标 0 到当前位置”这个子数组。

还有个顺序问题：必须先判断pre_sum - k是否在哈希表里，再把当前pre_sum放进去。为什么？因为题目要求子数组必须是非空的，如果先把当前前缀和放进去，那么当K=0时，你会把当前前缀和自己减自己算成一种情况，导致多计数。这个坑我在面试模拟里见过无数回，每次都想拍桌子。

3.2 和能被 K 整除的子数组：同余定理登场

这道题是上面的加强版：统计有多少个连续子数组的和能被 K 整除。思路依然是利用前缀和。设pre[i]是前 i 项和，那么子数组[j, i]的和能整除 K，等价于pre[i] - pre[j]能被 K 整除。模运算告诉我们，这等价于：

pre[i] % K == pre[j] % K

也就是说，两个前缀和对 K 取模的余数相同，那么它们之间的区间和就一定是 K 的倍数。于是我们只需要用哈希表统计每个余数出现的次数，每遇到一个余数，它历史出现的次数就是要累加的数量。

但是，这里有一个极其经典的坑：当前缀和为负数时，Python 和 Java 的取模结果不一样。比如-1 % 5，Python 的结果是 4，Java 的结果是 -1。如果我们在哈希表里存的是负数模数，同一段区间可能被错误地分成两类。解决方案是在取模后统一转正：

mod = pre_sum % k mod = (mod + k) % k

实现如下：

def subarrays_div_by_k(nums, k): mp = {0: 1} pre_sum = 0 count = 0 for x in nums: pre_sum += x mod = pre_sum % k # 统一转为非负余数 mod = (mod + k) % k count += mp.get(mod, 0) mp[mod] = mp.get(mod, 0) + 1 return count

这道题的高频程度很高，因为它不仅考了前缀和，还顺便考了你对取模、负数、哈希表的综合理解。很多看起来不相关的题，比如“左右两边子数组和相等”“奇偶性相同的区间”，都能用同一种模式去套。

3.3 0 和 1 数量相同的连续数组：把 0 变成 -1 的神来之笔

这道题要求找到最长的连续子数组，使得子数组中 0 和 1 的数量相同。第一次见可能会想用滑动窗口，但实际上这不是单调窗口问题，最稳的解法还是前缀和。核心技巧：把数组里的 0 全部当成 -1，那么“0 和 1 数量相同”就等价于“这个子数组的和为 0”。

于是问题变成：求最长的和为 0 的连续子数组。这需要我们在遍历过程中，用哈希表记录每个前缀和第一次出现的位置。因为要求最长，所以一旦某个前缀和再次出现，说明从第一次出现位置的下一个元素到当前下标之间，数组和就是 0。

def find_max_length(nums): mp = {0: -1} pre_sum = 0 ans = 0 for i, x in enumerate(nums): pre_sum += 1 if x == 1 else -1 if pre_sum in mp: ans = max(ans, i - mp[pre_sum]) else: mp[pre_sum] = i return ans

这里的关键细节是：只有第一次出现某个前缀和时才记录位置，后面再出现都不更新。这样能保证区间尽可能长。

4. 第三梯队：二维压缩与最大子矩阵

4.1 最大子矩阵和：把二维问题压成一维

最大子数组和问题大家应该不陌生，经典动态规划就能搞定。但如果把题目放到二维矩阵里，让你找一个子矩阵，使矩阵内所有元素之和最大，那就得结合二维前缀和了。我常用的方法是“行压缩”：枚举矩阵的上下边界，把上下边界之间的每一列的元素累加成一个一维数组，然后在这个一维数组上跑最大子数组和算法。

当然，这里我们用前缀和直接加速列累加的过程。假设我们枚举了上边界top和下边界bottom，那么每一列j在这两条边界之间的和，等于二维前缀和给出的结果：ps[bottom+1][j] - ps[top][j]。这样，我们不用每次都重新累加列，只需要 O(1) 取出来，拼成一个临时数组，然后求“最大子数组和”。

def max_submatrix(matrix): m, n = len(matrix), len(matrix[0]) # 构造二维前缀和 ps = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m): for j in range(n): ps[i+1][j+1] = ps[i][j+1] + ps[i+1][j] - ps[i][j] + matrix[i][j] ans = float('-inf') for top in range(m): for bottom in range(top, m): cur = 0 best = float('-inf') for col in range(n): col_sum = ps[bottom+1][col+1] - ps[top][col+1] - ps[bottom+1][col] + ps[top][col] # 经典最大子数组和 cur = max(col_sum, cur + col_sum) best = max(best, cur) ans = max(ans, best) return ans

枚举上下边界是O(m^2)，每一层遍历列是O(n)，总体复杂度O(m^2 * n)。矩阵规模不大时这个方案非常舒服。它的核心思路其实是“降维打击”：二维问题变成一维问题，一维问题再用经典算法解决。

4.2 子矩阵和不超过 K 的极值问题

如果题目变成“找和不超过 K 的最大子矩阵和”，难度直接升了一档。最稳妥的思路还是行压缩，把每两行之间的列和变成一维数组，然后问题就变成了：在一个一维数组中，求不超过 K 的最大子数组和。

在一维版本里，如果其中所有元素都是正数，可以用滑动窗口。但因为有负数，滑动窗口不成立，我一般会配合前缀和与二分：先算出一维数组的前缀和，遍历每个pre[i]，看之前是否有前缀和pre[j] >= pre[i] - K，因为pre[i] - pre[j] <= K所以pre[j] >= pre[i] - K，并且子数组和尽可能大的话，我们希望pre[j]尽量靠近pre[i] - K的上界，所以用有序集合维护历史前缀和，然后二分查找大于等于pre[i] - K的最小值。

from bisect import bisect_left from sortedcontainers import SortedList # 或自己实现平衡树 def max_submatrix_sum_no_more_than_k(matrix, k): m, n = len(matrix), len(matrix[0]) # 构造二维前缀和 ps ... ans = float('-inf') for top in range(m): for bottom in range(top, m): arr = [] for col in range(n): col_sum = ps[bottom+1][col+1] - ps[top][col+1] - ps[bottom+1][col] + ps[top][col] arr.append(col_sum) # 一维数组 arr 中找最大且不超过 K 的子数组和 pre = 0 sl = SortedList([0]) for x in arr: pre += x target = pre - k idx = bisect_left(sl, target) if idx < len(sl): ans = max(ans, pre - sl[idx]) sl.add(pre) return ans

这个题目适合有一定基础的人去啃，因为它把二维前缀和、一维前缀和、有序集合、二分查找全部串起来了。

4.3 行压缩法为什么是万金油

这类二维题目的通解套路我归纳成三步：第一步，枚举上下边界，把问题压成一维；第二步，在一维数组上应用前缀和或滑动窗口；第三步，用合适的数据结构维护需要的历史信息。记住这个流程，你碰到“最大子矩阵和”“子矩阵和要求等于某个值”“子矩阵平均数最大”这类题目时，心里会比较有底。

5. 第四梯队：前缀积与前缀思想迁移

5.1 除自身以外数组的乘积：前缀积和后缀积的结合

这道题的经典问法：给定一个数组，返回一个新数组，其中每个位置的值是原数组中除了该位置以外所有元素的乘积，要求不能用除法，并且尽量在 O(n) 时间内完成。虽然名字没有“前缀和”，但它本质上是前缀思想在“乘法”上的迁移。

思路是这样：先从左往右扫一遍，维护“当前位置之前所有元素的乘积”，存在left数组里；再从右往左扫一遍，维护“当前位置之后所有元素的乘积”，存在right数组里；最终答案是left[i] * right[i]。

def product_except_self(nums): n = len(nums) left = [1] * n right = [1] * n for i in range(1, n): left[i] = left[i-1] * nums[i-1] for i in range(n-2, -1, -1): right[i] = right[i+1] * nums[i+1] ans = [left[i] * right[i] for i in range(n)] return ans

如果题目要求空间复杂度 O(1)（不算输出数组），可以直接拿结果数组当left，然后用一个变量滚动维护right。这道题的高频点是它考察了“方向相反的两次遍历”这种思想，跟前缀和背后的“预处理再查询”是同一种味道。

5.2 前缀异或：处理区间异或问题

前缀思想最早出现在和上，但异或也可以。求一个数组某个区间的异或和，可以定义px[i] = px[i-1] ^ a[i-1]，然后区间[l, r]的异或和等于px[r+1] ^ px[l]，因为异或运算中x ^ x = 0，相同部分会被抵消。这对某些面试题很有用，比如“找数组中出现奇数次的数”“求某个区间内所有数异或的结果”。我提这个是想提醒你：前缀和真正的灵魂是“可逆运算”。加减、异或都是可逆的，乘除也是，但如果你遇到的是max、min这种不可逆运算，前缀和就推不动了。

5.3 什么时候该想到前缀和

我自己的判断标准有三条。第一，题目涉及连续区间，而且区间范围特别大，查的特别频繁；第二，题目要求的统计量可以通过“两个前缀状态的差值”表达；第三，你能用哈希表、有序集合等结构在遍历过程中记录历史信息。如果三条里面占了两条，基本可以很自信地往前缀和方向去思考。如果不满足，“别忘了先排序”或者“考虑用树状数组”也可以作为备用方案。

6. 实战中的高频坑与排查手册

6.1 索引偏移是最大的敌人

前缀和写错了，十有八九是下标问题。我见过太多人把pre[i]理解成“包含a[i]的前缀和”，然后查询时又用pre[r] - pre[l-1]，绕来绕去最终把自己绕晕。我的建议是固定使用“pre[i]表示前 i 项和，不含a[i]”这一种定义。查询区间[l, r]时，闭区间统一用pre[r+1] - pre[l]。这个规则一旦确定，所有题目都沿用，不要今天一套明天一套。

6.2 负数取模的坑

刚才已经强调过，负数取模在不同语言里行为不一样。如果你做题环境是 Python，-1 % 5得到 4，这是数学上的“非负余数”，其实是方便我们的。但如果用 Java 或者 C++，-1 % 5得到 -1，这时候就必须手动(mod + k) % k。我建议不管用什么语言，统一写一次转正操作，避免换语言时出错。

6.3 哈希表的初始化与更新顺序

凡是“和为 K 的子数组”这类计数题，容易错的点有两个。一是忘记{0: 1}初始化，导致漏算从开头开始的合法子数组；二是“先查询再插入”顺序反了，变成先插入，导致空子数组被算入。我建议在代码里把这两行顺序写到条件里，养成肌肉记忆：先查，再存。

# 正确顺序 if pre_sum - k in mp: count += mp[pre_sum - k] mp[pre_sum] = mp.get(pre_sum, 0) + 1

6.4 二维前缀和的正负号永远在考验你

二维的前缀和公式里有一个减一个加，很多人会记成“两加两减”，结果边界就错了。我有一个笨但有效的记忆方法：查询(r1,c1)到(r2,c2)时，先用大矩形的右下角(r2,c2)，然后剪掉上方和左边的矩形，最后把被剪了两次的左上角补回来。这个口诀每次都能救我一命。

6.5 整型溢出和极大值

如果数组里都是大整数，前缀和有可能超过语言默认的整数范围。Python 不需要担心，但 Java 或者 C++ 要小心int溢出，建议直接用long。另外求“最大子矩阵和”时，初始值不要设成 0，而是Integer.MIN_VALUE或float('-inf')，否则全负数矩阵会直接算错。

7. 想在前缀和基础上再进阶，可以看这几条支线

7.1 差分数组：前缀和的逆行

前缀和是“从区间到点”的快速查询工具，差分数组则是“从点到区间”的快速更新工具。如果你有一个数组，要反复执行“把[l, r]区间每个元素加 val”的操作，最后才询问单点值，暴力更新会非常慢。差分数组的做法是只改diff[l] += val和diff[r+1] -= val，最后做一次前缀和还原出原始数组。两者互为逆运算，掌握了前缀和再学差分，就是顺水推舟的事。

7.2 前缀和 + 单调性优化

如果题目中的前缀和数组天然具有单调性，比如原数组全是非负数，那么前缀和就是非递减的。这种情况下，“是否存在某个区间和小于等于目标值”这样的问题，可以用双指针滑动窗口代替二分，甚至直接用贪心。很多前缀和变题会跟这种单调性结合，面试官看到你能讲出这层关系，印象分会高不少。

7.3 什么时候别硬套前缀和

前缀和不是万能的。如果数组会频繁原地更新，那每次更新都要改前缀和数组，复杂度反而退化。这种场景应该考虑树状数组或线段树。另外，如果题目要求的是“最大最小值区间查询”，前缀和没法直接表达这个信息，你应该考虑稀疏表（ST 表）或线段树。选数据结构的原则永远是：你的操作是什么，数据会不会变，查询是什么类型。这几个问题想清楚了再动手，比默写模板重要得多。

我个人在实际操作中的体会是：前缀和题目的代码量都很小，真正的难点全在“能不能在一分钟内推导出公式”。所以我每次刷到新题，都会先强制自己画一个数组，然后把pre数组手写出来，再标出哪两个前缀之间的差对应题目要求的区间。这个动作看起来笨，但确实能大幅降低出错率。最后再分享一个小技巧：准备一个自己的模板本，把一维前缀和、二维前缀和、前缀和加哈希、前缀和加二分这四套模板都提前写好，面试前过一遍，实战时直接套用，你会发现自己变得特别稳。