说实话前缀和这名字听起来挺劝退的感觉像是数学课里才会出现的东西。但你要是真把它搞明白了会发现它其实是刷题性价比极高的一块内容——概念极其简单就那么一个累加公式却能串起一堆看似毫无关联的高频题区间求和、子数组计数、二维矩阵查询、甚至随机权重采样。我见过不少朋友刷了几百道题遇到连续子数组和等于 K这类题还是要憋半天原因只有一个他没意识到这题考的就是前缀和。这篇文章我从实际刷题和面试准备的视角出发挑了题库里出现频率最高、也最典型的 8 道前缀和题目按难度递进逐一拆解。每道题我都会讲清楚思路是怎么来的、代码怎么写、复杂度是多少、以及哪里有坑。适合三种人看一是刚开始系统刷算法、想把基础打扎实的同学二是面试前突击、需要快速过一遍高频题型的求职者三是刷过一遍但总是看题会、上手废想搞清楚套路本质的进阶选手。1. 前缀和到底是什么一个例子讲清楚先别急着看公式我们从一个最朴素的问题出发。假设你手里有一个数组 nums长度 n现在要你反复回答下标 left 到 right 之间所有元素的和是多少。最笨的办法是每次查询都从 left 跑到 right 加一遍单次查询 O(n)。如果查询来了 m 次总复杂度就是 O(mn)数据一大基本就废了。前缀和的做法是提前算好一个 pre 数组让 pre[i] 表示原数组前 i 个元素的累加和也就是 nums[0] 加到 nums[i-1]。这样区间 [left, right] 的和就可以直接算出来sum(nums[left..right]) pre[right 1] - pre[left]来走一个具体例子。nums [3, 1, 4, 1, 5, 9, 2, 6]构建出来的 pre 是下标 i012345678pre[i]0348914232531注意 pre 的长度是 n1pre[0] 固定是 0。现在求区间 [2, 5] 的和也就是 nums[2] 到 nums[5]4 1 5 9 19。用公式算pre[6] - pre[2] 23 - 4 19完全一致。你可能会问为什么不把 pre[i] 定义成前 i1 个元素的和也就是 pre 和 nums 下标对齐那样的话求 [2,5] 就得写成 pre[5] - pre[1]而且 left 0 的时候你还得特判。多开一位下标对齐了不说所有边界情况全部消失这是一个你迟早会感激的设计。所以前缀和干的事情就一句话把重复计算的区间和提前压缩成两个前缀和的差值。预处理 O(n)之后每次查询 O(1)。这就是用空间换时间最直白的体现。2. 一维与二维前缀和的构建细节决定成败一维前缀和构建代码非常简单但有几个细节我建议你在纸上过一遍别光看def build_prefix(nums): n len(nums) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] nums[i] return pre这里最关键的一点是 pre[i 1] pre[i] nums[i]而不是 pre[i] pre[i - 1] nums[i]。后者也不是不能写但要多一堆下标判断还容易在 i 0 时越界。面试现场写错下标是大忌所以我个人一直坚持用错开一位的写法。另一个注意点是 pre 的类型数组元素可能是负数也可能累加结果超出 int 范围Python 无所谓但如果你用 C 或 Java记得考虑用 long否则溢出会让你查半天都不知道错在哪。二维前缀和就是同样的思路推广到平面。pre[i1][j1] 表示从矩阵左上角 (0,0) 到 (i,j) 这个矩形区域内的所有元素和。构建时要用一个容斥公式pre[i1][j1] pre[i][j1] pre[i1][j] - pre[i][j] matrix[i][j]为什么是加左加上再减左上因为 pre[i][j1] 和 pre[i1][j] 两个矩形区域有重叠部分重叠的就是 pre[i][j] 那一块所以必须先减去它再加当前格子的值。代码是这样的def build_prefix_2d(matrix): m, n len(matrix), len(matrix[0]) pre [[0] * (n 1) for _ in range(m 1)] for i in range(m): for j in range(n): pre[i 1][j 1] (pre[i][j 1] pre[i 1][j] - pre[i][j] matrix[i][j]) return pre查询子矩阵 (row1, col1) 到 (row2, col2) 的和用的是同一个容斥思路pre[row21][col21] - pre[row1][col21] - pre[row21][col1] pre[row1][col1]我的经验是二维前缀和公式特别容易把符号记反。别硬背你就在脑子里画一个 2x2 的小矩阵手动算一遍最多两三次这个公式就长在你脑子里了。还有个细节pre 数组第 0 行和第 0 列全都是 0这和一维多开一位是同一个道理所有边界情况统一处理不需要在循环里写 if。3. 八道高频题逐一拆解接下来是重头戏。我选的这 8 道题是从题库里反复出现的题里筛出来的覆盖了前缀和的所有典型用法。先给个总览题号题目特征核心考点难度1数组区间和检索不可变一维前缀和模板简单2二维矩阵区域和检索二维前缀和 容斥中等3和为 K 的子数组前缀和 哈希表中等4和可被 K 整除的子数组前缀和 同余中等5寻找数组的中心下标前缀和逆向思维简单6连续数组0/1 映射 哈希中等7除自身以外数组的乘积前缀思想的迁移中等8按权重随机选择前缀和 二分中等3.1 第一题数组区间和检索这题就是第一节里说的那个场景直接给一个类要求初始化时做好预处理然后支持反复查询。class NumArray: 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 sumRange(self, left, right): return self.pre[right 1] - self.pre[left]代码就这么短。这里想强调三个点都是面试官爱追问的第一为什么初始化复杂度是 O(n) 而查询是 O(1)如果你把预处理去掉每次查询直接遍历那 m 次查询就是 O(mn)数据量一大必然超时。第二pre[left] 里存的是 nums[0] 到 nums[left-1] 的和所以减掉它正好把区间外的部分全部消掉这就是前缀和的核心思想——两个前缀的差就是一个区间。第三如果题目改成数组可变、支持更新和查询那前缀和就不合适了得换树状数组或线段树这种延伸问题建议你提前准备一下。3.2 第二题二维矩阵区域和检索一维会了二维就是套公式。题目给了矩阵反复查询任意子矩阵的和要求每次查询 O(1)。class NumMatrix: def __init__(self, matrix): m, n len(matrix), len(matrix[0]) self.pre [[0] * (n 1) for _ in range(m 1)] for i in range(m): for j in range(n): self.pre[i 1][j 1] ( self.pre[i][j 1] self.pre[i 1][j] - self.pre[i][j] matrix[i][j] ) def sumRegion(self, row1, col1, row2, col2): return ( self.pre[row2 1][col2 1] - self.pre[row1][col2 1] - self.pre[row2 1][col1] self.pre[row1][col1] )我见过很多人在构建时把公式写成 pre[i1][j1] pre[i][j] 左边 上面漏掉了减去重叠部分结果查询结果总是偏大。你只要记住那个 2x2 小矩阵的例子就不会犯这个错。另外一个容易出错的地方是查询时四个角的下标要各自加 1很多人在这一步直接套构建公式就会下标错位。3.3 第三题和为 K 的子数组这道题可以说是前缀和 哈希表的代表作也是面试里出现频率极高的题。题目要求统计有多少个连续子数组的和恰好等于 k。暴力做法是枚举所有起点和终点O(n²) 直接超时。优化的关键思路是子数组 [i1, j] 的和可以写成 pre[j] - pre[i]。我们边遍历边记录当前位置之前出现过的前缀和那么对于当前前缀和 pre只要之前出现过 pre - k就说明存在某个起点能让这一段的和等于 k。def subarraySum(nums, k): count 0 pre 0 mp {0: 1} # 前缀和为 0 的情况初始出现 1 次 for num in nums: pre num if pre - k in mp: count mp[pre - k] mp[pre] mp.get(pre, 0) 1 return count这里有两个细节必须说清楚。第一mp[0] 1 表示什么都不选时前缀和为 0这样当 pre 本身就等于 k 时pre - k 0也能被正确统计到。第二必须是先查 mp 再把自己加进 mp顺序反了的话会把当前这个前缀和自己匹配上导致多算。这个顺序问题我在后来的面试模拟里见人栽过好几次。还有一个很自然的追问如果题目要的是和等于 k 的最长子数组长度怎么办思路几乎一样只是哈希表里存的从出现次数变成第一次出现的位置后面第六题会用到这个变体。3.4 第四题和可被 K 整除的子数组这题和上一题长得像但坑更多。题目要求统计有多少个子数组的和能被 k 整除。数学上子数组 [i1, j] 的和能被 k 整除等价于 pre[j] - pre[i] 能被 k 整除这又等价于 pre[j] % k pre[i] % k。所以问题变成了边遍历边计算当前前缀和对 k 的余数统计相同余数出现了多少次。每出现一个新的相同余数它就能和之前所有同余的位置各组成一个合法子数组。def subarraysDivByK(nums, k): count 0 pre 0 mp {0: 1} for num in nums: pre num mod pre % k if mod in mp: count mp[mod] mp[mod] mp.get(mod, 0) 1 return count这题最大的坑不在思路而在语言特性。Python 的 % 运算对负数是向负无穷取整的所以 (-1) % 5 的结果是 4而不是 -1。数学上 -1 和 4 对 5 同余所以这个结果恰好是我们要的。但如果你用 C 或 Java-1 % 5 结果是 -1直接拿去查哈希表就错了。正确的做法是先转正int mod ((pre % k) k) % k;。我在实际面试里被问过这个细节回答不上来会很减分建议不同语言的朋友都留个心眼。3.5 第五题寻找数组的中心下标这题看起来和前缀和无关但恰恰是考察你懂不懂前缀和的本质的一道题。题目要求找到一个下标 i使得 nums[i] 左边所有元素之和等于右边所有元素之和。如果存在多个返回最左边那个。思路其实不需要真的建 pre 数组。先求出整个数组的总和 total然后从左往右遍历维护一个 left_sum。对于下标 i右边元素之和就是 total - left_sum - nums[i]所以只要 left_sum 等于这个值i 就是答案。def pivotIndex(nums): total sum(nums) left_sum 0 for i, num in enumerate(nums): if left_sum total - left_sum - num: return i left_sum num return -1这里要注意的是判断时机必须在更新 left_sum 之前判断。因为 left_sum 定义是当前下标左边的元素和如果你先加了 num 再判断计算的就变成包含当前元素了。另外一个细节是题目要求返回最左边的下标所以从左往右扫遇到第一个满足条件的直接返回即可。这题想传达的是前缀和不一定要显式开数组很多时候只需要一个运行中的累加和配合上合适的等式就足够了。这种写法在代码里更轻量也更容易避免下标计算错误。3.6 第六题连续数组这题属于前缀和的进阶变体第一次见的人通常反应不过来。题目给一个二进制数组只含 0 和 1要求找到含有相同数量 0 和 1 的最长连续子数组。核心转换很巧妙把 0 看成 -1把 1 看成 1。这样一来子数组中 0 和 1 的数量相同就等价于子数组的和为 0。而子数组和为 0又等价于两个位置的前缀和相等。于是问题变成找两个相同前缀和之间最远的距离。def findMaxLength(nums): mp {0: -1} # 前缀和为 0 最早出现在下标 -1 pre 0 ans 0 for i, num in enumerate(nums): pre 1 if num 1 else -1 if pre in mp: ans max(ans, i - mp[pre]) else: mp[pre] i return ans这题有两个关键细节。第一mp 初始化是 {0: -1}因为当前缀和为 0 时意味着从数组开头到当前位置这一段本身就是0 和 1 数量相同的而前缀和为 0 的最早位置应该是在下标 -1也就是数组开始之前。第二哈希表里只存第一次出现的位置绝不更新。因为你要的是最长距离位置越靠前和当前下标的距离越大后面再遇到同样的前缀和最早的位置永远是最优的。这个0/1 映射 前缀和相等找距离的套路非常经典换个数就能变成最长不含重复字符之外的很多变体题值得反复品味。3.7 第七题除自身以外数组的乘积题目要求返回一个数组其中每个元素是除了 nums[i] 以外所有元素的乘积并且题目特别规定不能用除法。这个限制很关键否则直接算总乘积再逐个除就完事了。不能用除法那就用左边乘一遍右边乘一遍的思路。这其实就是前缀和思想的迁移——前缀和用加法累加这里改成累乘。先从左到右算一遍前缀积存到答案数组里再从右往左遍历用一个变量维护右侧累乘乘到对应的答案位置上。def productExceptSelf(nums): n len(nums) ans [1] * n for i in range(1, n): ans[i] ans[i - 1] * nums[i - 1] # ans[i] 左侧所有元素的乘积 right 1 for i in range(n - 1, -1, -1): ans[i] * right # 乘上右侧所有元素的乘积 right * nums[i] return ans举个例子验证一下。nums [1, 2, 3, 4]第一遍循环后 ans [1, 1, 2, 6]这分别是每个位置左侧元素的乘积。第二遍从右往左right 依次是 1、4、12、24乘上去之后 ans 变成 [24, 12, 8, 6]正确。这题的空间复杂度做到了 O(1)不算输出数组是这个解法最值得称道的地方。这里有个面试延伸点如果数组里有 0 怎么办按这个写法其实天然兼容——某个位置左侧或右侧出现 0乘积就会变成 0不会影响其他位置结果的正确性。你可以在脑子里验证一个含 0 的例子会发现它依然对。3.8 第八题按权重随机选择这题是前缀和比较冷门但很有意思的应用出现在不少公司的笔试里。题目给一组权重 w要求按权重比例随机返回下标。比如 w [1, 3]那么返回下标 0 的概率应该是 1/4返回下标 1 的概率是 3/4。思路是把权重看成区间的长度构建前缀和数组 prepre[i] 表示前 i 个权重的累加这样整个权重和 total 就是一个大区间每个下标对应一段长度等于其权重的小区间。生成 [1, total] 的随机数看它落在哪个小区间里就返回谁。定位区间用二分因为前缀和是单调递增的。import random class Solution: def __init__(self, w): self.pre [0] for x in w: self.pre.append(self.pre[-1] x) self.total self.pre[-1] def pickIndex(self): target random.randint(1, self.total) # 找第一个前缀和 target 的位置 left, right 0, len(self.pre) - 1 while left right: mid (left right) // 2 if self.pre[mid] target: right mid else: left mid 1 return left - 1为什么要随机数从 1 开始而不是从 0 开始因为 pre 是从 0 开始的如果随机到 0就会落到哨兵位置上导致下标变成 -1这是边界错误。另外返回值为什么要 left - 1因为 pre 的长度是 n1pre[1] 对应的是第 0 个权重所以第几个前缀和和真实下标之间差一位。二分那里用的是找左边界的写法也就是找第一个满足 pre[mid] target 的位置这和你平时写的那种找精确值的二分不太一样要专门练一下。C 里可以直接用 lower_bound 一行搞定但懂原理总比背函数强。4. 从八道题里提炼的通用套路八道题过完如果只是记住了代码那过两周肯定忘。真正值钱的是把这八道题背后的通用套路提炼出来。我总结成三条你在别的前缀和题目里几乎都能套用。套路一区间问题就是差值问题。前缀和最核心的一句口诀是子数组和 两个前缀和的差。无论是第一题的直接相减、第三题的 pre - k 查找、第四题的同余相等还是第六题的前缀和相等本质上都是两个前缀之间的关系决定了一段区间是否满足条件。拿到一道区间题先问自己能不能把条件改写成某两个前缀和之间满足某某关系如果能前缀和就大概率能用。套路二哈希表负责记住过去。当我们需要知道在当前位置之前有多少个前缀和满足某条件时哈希表就是标配。第三题存次数第六题存最早位置第四题存同余余数的次数区别只在 map 的 value 语义。这个组合太常考了我建议你把这三道题放一起反复做直到形成肌肉记忆。套路三前缀和可以当基础设施和其他结构搭配。第八题告诉我们前缀和天生有序可以用来做二分的查找表接雨水那类题用的是从左扫一遍、从右扫一遍的双向前缀思想第七题把累加换成累乘是前缀和的变体。所以学到后面你会发现前缀和不只是一个模板更是一种思维习惯任何需要连续一段的某种聚合信息的场景都可以先想想能不能用前缀的方式预处理。5. 实战中的坑与调试建议最后这部分是我自己刷题和帮别人 review 代码时反复看到的坑写出来给你提个醒。坑一pre 数组长度和下标错位。十个人里有八个第一次写前缀和都会栽在这。记住一句话pre 长度是 n1pre[i] 表示前 i 个元素的和查询区间 [l, r] 时用的是 pre[r1] - pre[l]。如果出现越界、结果差一个元素、left0 时特判等问题基本都是这里错了。调这类 bug 最快的办法是把 pre 数组打印出来和手算的累加表逐项对比。坑二哈希表的初始化时机。第三题和第四题都要在循环前初始化 mp[0] 1它的语义是空区间的前缀和为 0第六题则是 mp[0] -1因为要存位置而不是次数。初始化错了答案通常会差 1而且很难一眼看出来。我的习惯是每次写完这类题专门验证一下pre 第一次等于 k这个场景看结果对不对。坑三负数取模的语言差异。前面说过Python 取模结果非负对同余类题目是友好的但 C/Java 不是。如果你平时用 Python 刷题突然换语言写第四题很容易踩到。稳妥做法是在脑子里标记一下凡是涉及负数取模、又要求余数去哈希表查的都必须把余数转成非负。坑四二维容斥符号。二维前缀和的构建和查询都涉及四个项符号顺序是加左加上减左上。我见过有人把构建的公式背熟了查询时却忘了查询本质上也是容斥四个项的符号照样是减两加一。遇到这种问题画一个 3x3 的小矩阵手算一遍比盯着代码看一个小时都管用。坑五随机权重里的边界。第八题的二分边界和返回值的 -1 偏移是这类题最容易错的地方。建议你在纸上把 pre [0, 1, 4, 6] 这个例子完整走一遍把 target 1、2、4、6 分别对应到哪个下标标出来彻底理解了再上手写代码比死记模板靠谱得多。关于调试我再分享一个我常用的方法写前缀和题目时构造一个长度为 5 到 8 的随机小数组手算出答案再和程序输出比对。小数组能让你在出错时一眼看出是哪一位不对。尤其是哈希表类的题目把 mp 的变化过程打印出来基本上一轮就能定位问题。我自己在实际刷题中体会最深的一点是前缀和的题目代码往往不超过二十行难的是识别出这题能用前缀和。所以刷题时别急着看题解先强迫自己回答一个问题——这道题的条件能不能改写成一个关于前缀和的等式这个思考习惯一旦养成你会发现前缀和题其实是刷题里最有手就行的一类。