很多刷题的朋友第一次被“前缀和”这三个字击中都是在“和为 K 的子数组”这道题上。两重循环的暴力版本五分钟写完了一提交直接超时然后才意识到事情没那么简单。等到后来把“和可被 K 整除的子数组”“连续数组”“矩阵区域和”这几道题连着刷完你会发现它们根本不是四道独立的题而是同一个思想在不同维度上的变体——用累积和来代替区间求和把 O(n²) 甚至 O(n³) 的枚举压缩到 O(n)。这篇文章我就按自己学习的顺序把这四条路串起来讲清楚。不管你是在准备面试还是单纯想把算法基础打扎实我都建议按下面的顺序读先搞懂前缀和数组的最基本定义再用“和为 K 的子数组”理解哈希表怎么配合它工作接着用“余数”视角看第二个变体然后进入最值问题“连续数组”最后升级到二维看“矩阵区域和”。每道题我都会把推导过程写出来不只是贴代码——因为面试的时候能讲清楚“为什么这么做”比默写代码有用得多。1. 先把“前缀和”这三个字拆开说透1.1 从一个最简单的求和场景开始假设有一个数组nums [1, 2, 3, 4, 5]我想频繁地计算任意区间[l, r]内所有数字的和。最直接的办法是写一个循环累加def range_sum(nums, l, r): total 0 for i in range(l, r 1): total nums[i] return total每次查询都是 O(r - l) 的时间。如果数组长度是 10^5查询次数也是 10^5那最坏情况就是 10^10 次操作直接把你送走。问题出在哪出在每次查询都把区间里的元素重新加了一遍而很多求和结果其实是重复的。前缀和的思路特别朴素我先从头到尾把“累计和”算好存下来之后任何区间和都通过两次减法得到不再碰原始数组。定义前缀和数组prepre[0] 0表示前 0 个元素的和是 0pre[i] nums[0] nums[1] ... nums[i-1]即前 i 个元素的和构造过程def build_prefix(nums): n len(nums) pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] nums[i - 1] return pre注意下标偏移pre[i]对应的是nums里前 i 个元素也就是nums[0...i-1]。这样设计不是故意为难你而是为了让pre[0] 0占住一个位置后面所有区间公式都不需要特判边界。1.2 区间和为什么变成了“两次减法”有了前缀和数组想求nums[l...r]的和直接算sum(l, r) pre[r 1] - pre[l]你可以把它理解成记账pre[r1]是到第 r 天为止总共花的钱pre[l]是到第 l-1 天为止总共花的钱两者一减就是第 l 天到第 r 天这期间花的钱。这里没有任何魔法就是累计额的减法。这个公式是整个前缀和家族的地基。后面四道题每一道都是在问这个“差值”等于什么、模什么、什么时候相等、以及怎么快速统计。2. 和为 K 的子数组哈希表在这里才是关键2.1 暴力做法为什么必挂题目要求统计所有和为 K 的连续子数组的个数。最直接的思路是枚举每个区间def subarray_sum(nums, k): n len(nums) ans 0 for i in range(n): total 0 for j in range(i, n): total nums[j] if total k: ans 1 return ans外层定起点内层累加终点。时间 O(n²)空间 O(1)。这个代码在数组长度 100 以内完全够用但一旦到 10^5 就彻底不行了。而且这里有个关键特性——nums里可能有负数所以不能用滑动窗口窗口右移时总和不一定变大左移时总和不一定变小双指针的前提“单调性”在这里根本不成立。2.2 核心等式是怎么推出来的我们用前缀和重新翻译一下“和为 K 的子数组”这句话。一个子数组nums[j...i]的和可以写成pre[i1] - pre[j] K移项得到pre[j] pre[i1] - K这个式子的意思是当我站在位置 i准确说是前缀和下标 i1的时候如果历史上有某个前缀和的值正好等于pre[i1] - K那么从那个位置到当前位置形成的子数组和就是 K。于是问题变成了遍历过程中我需要快速知道“已经出现过多少个前缀和它们的值等于某个特定值”。这种“历史出现次数”的查询天然就是哈希表的主场。2.3 哈希表初始化的正确姿势直接上代码def subarray_sum(nums, k): mp {0: 1} # 前缀和为 0 出现过 1 次 pre 0 ans 0 for x in nums: pre x if pre - k in mp: ans mp[pre - k] mp[pre] mp.get(pre, 0) 1 return ans很多人第一次写的时候会问为什么mp里要提前放一个{0: 1}原因很简单如果整个子数组从nums[0]开始比如nums [1, 2, 3], k 3那么pre[2] - pre[0] 3 - 0 3这个pre[j] pre[0] 0就是我们要找的历史前缀和。如果不把 0 放进去漏掉的就是所有从数组头部开始的子数组。你可以试一下把mp初始化为空答案会直接少掉好几种情况。这个错误我在初学阶段反复踩过不是记不住而是没真正理解pre[0]是那个“空数组的和”它也是合法前缀和。2.4 先查询还是先更新顺序里藏着个坑还有一个小细节循环里是“先查询再更新”。为什么顺序这么重要因为我们要找的子数组是“历史中已经完整出现过的前缀和”不包括当前这个位置刚形成的前缀和。如果k 0你先把当前pre放进了哈希表然后再查pre - k pre会把自己当成答案加进去导致多算一个长度为 0 的空子数组。虽然k 0在不少版本的题目里没有单独卡这个点但这是面试官很爱追问的细节养成“先查后存”的习惯能帮你躲掉这个坑。这道题的时间复杂度 O(n)空间 O(n)。数组里有负数也完全不影响因为我们只关心前缀和之间的差值不依赖任何单调性。3. 和可被 K 整除的子数组同余才是这个模型的灵魂3.1 从“相等”到“模相等”的思维升级第二道题换了个条件不要求子数组的和恰好等于 K而是要求能被 K 整除。暴力枚举每个区间再判断(sum % K) 0依然是 O(n²)同样过不了大数据。但用前缀和写一下条件就很有意思了(pre[i1] - pre[j]) % K 0根据模运算的性质等价于pre[i1] % K pre[j] % K翻译成人话两个前缀和除以 K 的余数相同那么它们之间的区间和一定能被 K 整除。所以这道题的根本不是“差值等于多少”而是“余数是否相等”。这和“和为 K 的子数组”的区别在于那边哈希表的 key 是前缀和的具体值这边的 key 是前缀和对 K 取模后的余数。统计的是每个余数出现了多少次答案就是把相同余数的前缀和两两配对。3.2 负数取模的坑必须单独说我先写了第一版代码def subarrays_div_by_k(nums, k): mp {0: 1} pre 0 ans 0 for x in nums: pre x mod pre % k ans mp.get(mod, 0) mp[mod] mp.get(mod, 0) 1 return ans然后拿 LeetCode 974 的官方例子跑了一遍nums [4, 5, 0, -2, -3, 1], k 5预期是 7。我在本地跑怎么跑都是错的最后发现是负数取模的锅。Python 里-1 % 5 4这在数学上是正确的保证结果落在[0, k)区间但如果你用 Java 或 C 写-1 % 5 -1结果就是负数。两个语言行为不一致就会导致同一套逻辑在 Python 下能过、Java 下挂掉。正确的统一写法是mod ((pre % k) k) % k先对pre取一次模加上k保证非负再取一次模兜底。这个写法在任何一个语言里结果都一样是模意义下处理负数的标准姿势。3.3 这个模型还能怎么变形一旦你接受了“余数相同”这个视角很多变体题都能一眼看穿。比如如果题目改成“和是 K 的倍数且不能为空数组”你只需要把mp[0]初始化为 0 而不是 1因为空子数组的和 0 确实是 K 的倍数但题目不要它。或者如果 K 可能是 0模运算直接崩了这时要单独讨论——只有前缀和完全相等时差值才是 0退化成“和为 0 的子数组计数”问题。还有一类高频变体是“奇偶性相减”子数组中奇数个数和偶数个数相等。把奇数记为 1、偶数记为 -1问题就变成了“和为 0 的子数组”本质上和这道题 K 取 2 是一样的。当你发现题目里出现了“数量相等”“差值固定”“模 K 同余”这些关键词优先往前缀和上想。完整代码def subarrays_div_by_k(nums, k): mp {0: 1} pre 0 ans 0 for x in nums: pre x mod ((pre % k) k) % k ans mp.get(mod, 0) mp[mod] mp.get(mod, 0) 1 return ans这道题的空间复杂度严格说是 O(min(n, k))因为余数最多只有 k 种哈希表不会无限膨胀。这也是同余类题目比普通前缀和题目空间上更可控的地方。4. 连续数组把“平衡”翻译成前缀和的差值语言4.1 0 变 -1一个四两拨千斤的小动作第三道题是给定一个只含 0 和 1 的数组找最长连续子数组使得 0 和 1 的数量相等。我第一次看到这题的时候想的是用两个计数器分别统计 0 和 1但发现很难快速判定“某个区间内两者数量是否相等”。后来看到一个技巧瞬间觉得自己的脑回路太直了——把所有 0 替换成 -1。这样“0 和 1 数量相等”就等价于“子数组所有元素的和为 0”。为什么假设子数组里有cnt0个 0、cnt1个 1替换求和为cnt1 - cnt0。cnt1 cnt0时这个和正好等于 0。一个计数问题被翻译成了求和问题于是直接落入前缀和的射程范围。4.2 存“最早出现位置”而不是“出现次数”现在要求的是“最长”子数组不是计数。回顾一下核心公式pre[i1] - pre[j] 0也就是pre[i1] pre[j]。一个前缀和值如果出现了多次意味着这些位置之间形成的区间和都是 0。要求最长我只需要保留这个前缀和值“第一次出现时的下标”。具体做法是哈希表 key 存前缀和的值value 存该值第一次出现的下标注意这里是下标不是次数。遍历时如果当前前缀和已经在哈希表里说明从最早出现的位置到当前位置形成的子数组和为 0更新答案max(ans, i - mp[pre])如果当前前缀和没出现过就把它存进去存的是当前位置下标4.3 为什么初始化是{0: -1}而不是{0: 0}这应该是这道题里问得最多的问题。pre[0] 0对应的是数组开始之前的位置下标是 -1。为什么是 -1假设整个数组都是合法答案比如nums [0, 1]替换后是[-1, 1]前缀和变化是0 → -1 → 0。遍历到最后一个元素时当前前缀和是 0而 0 在哈希表里对应的下标是 -1于是长度为1 - (-1) 2正确答案。如果你初始化{0: 0}算出来的长度是1 - 0 1就错了。这里pre[0]的语义是“一个元素都还没取时的前缀和”它的位置天然是 -1 而不是 0。很多初学者会直觉地把下标 0 和“最开始”画等号但在前缀和的世界里pre[0]和pre[1]之间隔了nums[0]这一个元素所以前者的位置必须是 -1 才能保证长度公式成立。完整代码def find_max_length(nums): mp {0: -1} pre 0 ans 0 for i, x in enumerate(nums): pre 1 if x 1 else -1 if pre in mp: ans max(ans, i - mp[pre]) else: mp[pre] i return ans注意一个细节当pre再次出现时哈希表里的下标要保留最早的那个不要更新。因为我们要的是最长越早出现意味着区间越长。这个逻辑和“和为 K 的子数组”里“每次出现都累加次数”正好相反一个是求最值一个是求计数哈希表里存的东西也随之变化。5. 矩阵区域和一维前缀和升级到二维5.1 二维前缀和数组的递推与容斥原理最后一道题把场景从数组拉到矩阵给定一个二维矩阵要求频繁查询任意子矩阵的元素和。这就是 LeetCode 304 的经典场景。一位前缀和是累加一条线二维前缀和则是累加一个矩形。定义S[i][j]表示从矩阵左上角(0, 0)到(i-1, j-1)这个矩形内所有元素的和。注意这里的下标依然从 1 开始计数S比原矩阵多一行一列。构造公式S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] matrix[i-1][j-1]这个公式你死记硬背也能写但面试时最好能讲清楚为什么有“加一个减一个”的加减抵消。假设我已经知道了绿色部分、蓝色部分和紫色部分的和现在要算整个大矩形的和加上S[i-1][j]上面区域加上S[i][j-1]左面区域发现左上角那块S[i-1][j-1]被加了两次要减掉一次最后加上matrix[i-1][j-1]这个新元素这就是容斥原理和你求两个圆并集面积时“A 面积 B 面积 - 重叠面积”用的是同一个逻辑。代码实现class NumMatrix: def __init__(self, matrix): if not matrix or not matrix[0]: return m, n len(matrix), len(matrix[0]) self.s [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): self.s[i][j] ( self.s[i-1][j] self.s[i][j-1] - self.s[i-1][j-1] matrix[i-1][j-1] ) def sum_region(self, row1, col1, row2, col2): return ( self.s[row21][col21] - self.s[row1][col21] - self.s[row21][col1] self.s[row1][col1] )5.2 任意矩形区域和的查询公式查询(row1, col1)到(row2, col2)的子矩阵和公式是sum S[row21][col21] - S[row1][col21] - S[row21][col1] S[row1][col1]同样可以讲出逻辑先拿整个大矩形S[row21][col21]减掉上方S[row1][col21]再减掉左方S[row21][col1]但左上角那部分被减了两次所以要加回来S[row1][col1]。注意四个下标全部要 1 或保持原值这是二维前缀和最绕的地方。我的经验是永远记住S比原矩阵多一圈 0所以原坐标(x, y)在S中对应(x1, y1)。把查询公式里的四个点对应到原矩阵上画一画比死记硬背靠谱得多。5.3 如果题目要的是“每个位置的方块和”标题里的“矩阵区域和”还可能指 LeetCode 1314 那种题给你一个矩阵和一个参数 k要求对每个位置(i, j)计算以它为中心、半径为 k 的正方形区域内所有元素的和。这种题其实是“二维前缀和 枚举”的组合。先用上面的方法构建好二维前缀和数组然后对于每个位置算窗口边界r1 max(0, i - k) c1 max(0, j - k) r2 min(m - 1, i k) c2 min(n - 1, j k)再做查询。整体时间复杂度 O(m × n)因为二维前缀和构建是 O(m × n)窗口查询是 O(1)。边界用max和min夹紧就不会出现坐标越界的问题。我见过不少人在这一步直接对着矩阵硬遍历窗口内的所有元素结果又带回 O(m × n × k²) 的复杂度。正确的思考路径是二维前缀和的价值在于“把任意子矩阵的求和变成 O(1)”而 1314 这类题只是一个“批量查询”的应用场景预处理一次处处复用。6. 从四道题提炼出一条可复用的解题链6.1 复杂度收益到底有多大把四道题的复杂度放在一起看收益更直观题目暴力最优复杂度前缀和方案空间开销和为 K 的子数组O(n²)O(n)O(n)和可被 K 整除的子数组O(n²)O(n)O(min(n, k))连续数组O(n²)O(n)O(n)矩阵区域和O(m × n × q)O(m × n) 预处