LeetCode 3070 这题我看到“元素和小于等于 k 的子矩阵的数目”这个标题时第一反应是“又来一个统计子矩阵的硬核题”。但真正读完题之后会发现它其实比很多同类题要友好——所有子矩阵必须以原矩阵左上角为起点也就是说我们只需要统计从(0,0)到(i,j)这些前缀区域里有多少个矩形区域的和不超过k。这不就是典型的二维前缀和场景吗而且这题还顺手考了一个很实用的小优化原地把原数组改造成前缀和矩阵额外空间做到 O(1)。我刷这类题多了以后最大的感受是二维前缀和本身不难难的是你能不能识别出“这题能用前缀和”以及实现时能不能把边界和溢出问题一次性处理干净。这篇就以 3070 为引子把二维前缀和、原地修改的思路、易错点和变式全部拆开讲清楚。适合正在刷数组/矩阵类题目的选手也适合想搞懂“为什么可以原地修改”原理的读者。1. 题目到底在问什么1.1 先读懂“元素和小于等于 k 的子矩阵”这句话原题给了一个m x n的整数矩阵grid还有一个整数k。要求返回矩阵中满足“元素和小于等于 k 的子矩阵”的数目。最关键的限制是这些子矩阵的左上角必须是(0,0)。换句话说题目并不是让你枚举任意位置任意大小的子矩阵而是只统计那些“从左上角出发、不断向右下扩展”的矩形区域。每一个这样的区域其实只由它的右下角坐标(i,j)唯一确定。所以问题就变成了有多少个(i,j)坐标使得以(0,0)为左上角、以(i,j)为右下角的矩形区域内所有元素之和不超过k。这个限制让问题难度瞬间降了一档。因为如果你要枚举所有可能的子矩阵左上角有m*n种选择右下角也有m*n种选择组合起来数量级非常大。而这里左上角固定最多只有m*n个候选区域每个候选区域对应一个前缀和。这也解释了为什么这类题总爱用“数目”而不是“最大值/最小值”来提问——它实际上就是一个计数问题而计数问题的关键通常是“有没有办法快速算和”。1.2 暴力做法能算但代价高得离谱先别急着上最优解我们看一下如果不用前缀和暴力会走到什么程度。最朴素的思路是枚举每一个符合条件的矩形左上角固定为(0,0)枚举右下角(i,j)然后再用一层循环累加这个矩形里的所有元素。这样光是求和部分就需要 O(m*n) 的时间总体复杂度直接到了 O(m²n²) 以上。稍微优化一点可以维护一个“逐行前缀和”对每一行先求横向累计值然后纵向逐行累加这样求一个矩形区域的和能降到 O(1)。但枚举右下角仍然需要 O(mn) 个位置每个位置计算一次 O(1) 的查询整体复杂度是 O(mn)。看起来不错等一下这里所谓的 O(1) 查询其实已经是前缀和了。如果完全没有前缀和概念而是老老实实每次重新累加那 m 和 n 稍微大一点比如 1000暴力就完全跑不动。这里放一张复杂度对比表方便直观感受做法枚举区域数量每个区域求和代价总时间复杂度额外空间纯暴力每次重新累加O(mn)O(mn)O(m²n²)O(1)行前缀和 纵向累加O(mn)O(1)O(mn)O(m)二维前缀和O(mn)O(1)O(mn)O(1) 或 O(mn)所以二维前缀和的核心价值就是“预计算一次查询无数次”。当 mn1000 时纯暴力是 10^12 级别的操作现代计算机也扛不住换成前缀和以后只要做 10^6 级别的计算属于闭眼能过的范畴。2. 前缀和是这类题的标准答案2.1 一维前缀和先回忆一下“前 i 项的和”二维前缀和听起来高大上本质上就是一维前缀和的扩展。所以先花 30 秒把一维的东西捡起来。假设有一个数组arr我们想快速求arr[l]到arr[r]这一段的和。常规做法是写个循环累加每次查询 O(n)。但如果我们提前算好一个pre数组其中pre[i] arr[0] arr[1] ... arr[i]也就是从 0 到 i 的累计和那么区间和就能这样算sum(l, r) pre[r] - pre[l-1]这里如果l 0则pre[-1]需要特殊处理通常直接判断为 0。这个公式特别好理解你用“到 r 为止的累计和”减去“到 l 之前为止的累计和”剩下来的自然就是[l, r]这一段。生活化的类比就是记账你看了上个月的累计余额和这个月的累计余额两者相减就是这一个月新增的收支。一维前缀和的优点是查询 O(1)缺点是它只能处理“连续区间”的和。一旦问题变成二维矩阵里的矩形区域就要把“线段”升级成“矩形面”。2.2 二维前缀和容斥公式是怎么来的二维前缀和的定义很自然S[i][j]表示从(0,0)到(i,j)这个矩形区域的所有元素之和。假如我们已经知道了S[i-1][j]、S[i][j-1]和S[i-1][j-1]怎么推出S[i][j]可以画一个矩形图来理解。S[i][j]这个大矩形等于“上面的矩形”加上“左边的矩形”但“左上角那块小矩形”被加了两次所以要减掉一次最后再加上当前格子grid[i][j]本身的元素值。用公式写就是S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] grid[i][j]这就是容斥原理在二维前缀和里的体现。关于“为什么多减不回来”的问题我当初学的时候也懵过明明加上了grid[i][j]为什么还要单独加因为S[i-1][j]和S[i][j-1]都没有包含当前格子的值它俩的交集S[i-1][j-1]也没有包含所以当前格子必须单独加上否则就漏算了。我们同样可以用累计余额来类比。如果你把“到 (i,j) 为止的区域”想成一张拼图先拼上边部分再拼左边部分中间重叠的一小块如果重复计入了就要剥掉一次。剥掉之后右下角那个“新加入的格子”还得单独贴上去。整个思路理顺了公式就永远不会写错。2.3 这题为什么要用“原地修改”经典的二维前缀和一般做法是开一个(m1) x (n1)的新数组多出来的一行一列专门用来做边界哨兵从而避免对i0或j0的额外判断。这种做法写起来很舒服但代价是需要 O(mn) 的额外空间。3070 这道题有个特殊条件我们最后只需要统计“有多少个前缀区域的和 ≤ k”并不需要保留原来的grid数据。既然不依赖原始值了那就完全可以在原数组上直接覆盖把grid[i][j]变成S[i][j]。这就是标题里“原地修改”的由来。这样做的好处很明显空间复杂度从 O(mn) 降到 O(1)代码也更紧凑。坏处是原始矩阵被破坏了调试的时候如果想对照原数据就麻烦一点。但从算法题的角度看只要题目没有要求保留原数组原地修改就是合理且推荐的优化。3. 原地修改的具体实现与代码3.1 递推公式和边界条件既然要原地修改那grid[i][j]在计算完成后存放的就是从(0,0)到(i,j)的前缀和。递推公式其实和二维前缀和完全一样grid[i][j] grid[i-1][j] grid[i][j-1] - grid[i-1][j-1] grid[i][j]原来的值注意右边最后一个grid[i][j]必须是“原始值”不是已经改过的值。所以写代码时最好先用一个临时变量保存原始值算完再写回去。如果我们直接在原坐标上做grid[i][j] grid[i-1][j] grid[i][j-1] - ...理论上也正确因为累加的右侧邻居都已经被更新成了前缀和但为了可读性建议还是显式保存一下原始值避免自己都被绕晕。边界情况就是第一行和第一列。当i0时grid[i-1][j]不存在按 0 处理当j0时grid[i][j-1]不存在也按 0 处理。不需要额外开哨兵数组只需要在代码里判断i 0和j 0。3.2 可直接运行的题解代码我常用的 C 写法是这样class Solution { public: int countSubmatrices(vectorvectorint grid, int k) { int m grid.size(); if (m 0) return 0; int n grid[0].size(); int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { // 保存当前格子的原始值 int cur grid[i][j]; // 加上上方矩形的前缀和 if (i 0) cur grid[i-1][j]; // 加上左方矩形的前缀和 if (j 0) cur grid[i][j-1]; // 减掉左上角重复计算的部分 if (i 0 j 0) cur - grid[i-1][j-1]; // 原地更新 grid[i][j] cur; // 统计答案 if (cur k) ans; } } return ans; } };这段代码里我特意用了cur接收原始值再计算因为一旦你直接改grid[i][j]后面想拿原始元素就比较麻烦了。当然也可以写成grid[i][j] (i 0 ? grid[i-1][j] : 0) ...这种一行式但牺牲一点可读性。刷题时我建议按自己最不容易犯错的方式来。如果平时用 Python 刷题思路一模一样class Solution: def countSubmatrices(self, grid: List[List[int]], k: int) - int: m, n len(grid), len(grid[0]) ans 0 for i in range(m): for j in range(n): if i 0: grid[i][j] grid[i-1][j] if j 0: grid[i][j] grid[i][j-1] if i 0 and j 0: grid[i][j] - grid[i-1][j-1] if grid[i][j] k: ans 1 return ansPython 版本直接原地累加也是安全的因为当前格子还没被修改过加号右边的grid[i-1][j]和grid[i][j-1]都已经是前缀和了。唯一需要注意的是 Python 列表里的整数不会溢出所以写起来更随意。3.3 正确性验证与复杂度分析手算一个最简单的例子来验证。假设grid [[1,2],[3,4]]k 4。按行从左到右计算i0, j0grid[0][0]保持 11 ≤ 4计数 1。i0, j1grid[0][1] 2 1 33 ≤ 4计数 2。i1, j0grid[1][0] 3 1 44 ≤ 4计数 3。i1, j1grid[1][1] 4 3 3 - 1 9注意这里写清楚当前原始值是 4上方grid[0][1]已经是前缀和 3左方grid[1][0]已经是前缀和 4左上grid[0][0]是前缀和 1所以cur 4 3 4 - 1 10。其实正确区域和是 123410。所以 10 4不计数。最终答案是 3。对照原矩阵确实只有三个从左上角出发的子矩阵满足和不超过 4分别是[1]、[1,2]和竖着的[1,3]。复杂度上两层循环遍历了每一个格子每个格子做常数次加法和减法所以时间复杂度是 O(mn)。额外空间只有几个临时变量所以是 O(1)。对于 m、n 在 1000 甚至更大一些的范围这个效率都能直接通过。4. 踩坑记录与易错点盘点4.1 数据范围与溢出问题这是我在实际提交里踩过最多次的坑。如果grid[i][j]本身有比较大的值比如 10^6而矩阵是 1000×1000那么整个矩阵的和可能达到 10^12 级别早就超出 C 的int范围。虽然 LeetCode 这题的数据范围可能没这么极端但谁也不知道测试数据会不会给一个边界值。最稳妥的做法是在累加时使用long long。C 代码可以先把grid[i-1][j]、grid[i][j-1]这些值转成long long再计算最后只有和k比较时才转回普通整数。如果你和我一样写的是int cur grid[i][j]遇到大数值前缀和时就可能溢出导致判断出错这种 bug 特别难查因为你肉眼看到的数字可能已经变成了负数。总结一个经验凡是涉及二维数组区域求和的题先瞟一眼数据范围再决定要不要用long long。这道题虽然很多人用int也能过但养成“大数先想 long long”的习惯能帮你省掉很多调试时间。4.2 边界情况空数组、k 为 0 或负数题目通常保证了矩阵非空但写通用代码时最好还是先判断grid.empty()否则访问grid[0]会直接报错。这算是个防御性习惯面试时能体现代码的健壮性。k 0的情况也值得注意。如果矩阵里所有元素都是非负数那前缀和是单调不减的只有全 0 的矩阵区域才会被统计。如果矩阵里还有负数情况就完全不同了前缀和不再是单调的你不能一看到某个格子大于 k 就提前break因为同一个方向再往后走加了负数之后和可能又变小了。这一点特别容易忽略。如果题目没有明确说明元素非负最安全的做法是老老实实遍历所有格子不要做任何“超过 k 就停止”的剪枝。如果确认元素非负可以加一个行内剪枝但也要小心别剪错因为即使当前这行越界下一行仍然可能从头开始满足条件。4.3 原地修改什么时候不安全原地修改看起来非常香但它不是万能的。如果后续还需要使用原始矩阵或者你要在同一个矩阵上跑多个不同的算法原地覆盖就会出问题。比如你想先统计“和 ≤ k1”的子矩阵数目再统计“和 ≤ k2”的数目如果第一个统计时已经把矩阵改成了前缀和第二个统计时原始值已经不存在了结果肯定不对。这种情况下应该怎么办呢两个选择要么开一个额外的二维数组保存原始值要么在输入进来的时候先复制一份备份。对于 LeetCode 这种单次调用的场景原地修改没问题但如果你在做完整的工程项目或者要进行多次查询建议还是老老实实开一个prefix数组把grid保持原样。还有调试上的坑。我见过不少初学者一边打印原矩阵一边打印前缀和矩阵结果因为数据被原地覆盖怎么对都对不上。遇到这种情况别怀疑自己眼睛先确认是不是原地修改造成的。我的习惯是在写原地修改代码时注释里明显标注“此操作会修改原数组”提醒自己也提醒读代码的人。5. 从这一题能带走的解题思路5.1 识别“子矩阵求和”类题目的特征刷题刷多了以后你会发现很多矩阵题目其实都在暗示你用前缀和。出现这些特征时第一反应就应该是前缀和题目里出现了“子矩阵”、“矩形区域”、“区域和”等字眼。需要多次查询某个矩形区域的和。需要统计满足某个和条件的区域数量。给出的矩阵规模比较大暴力循环明显跑不过。尤其是“左上角固定”这种条件基本就是送分信号。因为它让每个区域和右下角坐标一一对应统计数量就变成了统计坐标数量。识别出题型后再思考一个问题能不能原地判断标准很简单——题目是否允许我们修改原数组是否还有其他环节需要使用原始数据如果两个答案都是“不/不需要”那么原地修改就是一个免费的优化。5.2 类似变式与延展方向3070 只是二维前缀和的入门姿势。真正在比赛里遇到的变式往往更复杂但万变不离其宗。比如如果题目改成“所有子矩阵的元素和小于等于 k 的数目”左上角不再固定那就不能只用一个前缀和矩阵硬算了。常见做法是把每行的前缀和算好然后枚举上下边界把二维问题压成一维的“子数组和 ≤ k 的数目”再用前缀和 双指针或者前缀和 有序集合来统计。这个过程就是把二维前缀和和一维区间计数结合起来。再比如求“满足元素和 ≥ k 的最小矩形面积”可以在确定上下边界后利用一维前缀和的单调性做双指针把复杂度降到 O(m²n)。这些题的核心都是从“快速求区域和”开始的前缀和就是它们的最底层地基。遇到这类变式我的建议是先把标准二维前缀和写熟尤其是边界条件和容斥公式。你先能做到不假思索地写对S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] grid[i][j]再去学进阶玩法会轻松得多。这道题我提交过程中最大的体会是有时候最优解并不需要花哨的数据结构只需要你愿意在动手前多想一步“这个和能不能复用”。前缀和看起来简单但它让我养成了一个很好的习惯——看到区间和、区域和、统计数量这类关键词先把“预计算 查询”的思维模型套上去。另外就算能原地修改我也会顺手在注释里写清楚原数组会被覆盖避免自己过两天回头看代码时愣住。希望你做完这题也能掌握这个判断流程识别题型、确认数据范围、决定是否原地、最后再动手写循环。