我最早看到力扣 3070 这道题的时候第一反应是又要枚举左上角、右下角四个循环跑一遍了。等我把题面读了三遍才发现题目压根不是那个意思——它要统计的是“包含grid[0][0]的子矩阵”里元素和小于等于k的个数。这个“包含左上角”五个字一出来整个问题的难度直接降了一个大档左上角被锁死剩下的只是一个二维前缀和计数问题甚至可以把原数组就地改造成前缀和矩阵一趟扫描顺带数答案。这篇东西我打算完全按实际操作来讲。先说说题目为什么会被误读再说二维前缀和的递推公式为什么是那个样子最后给一套可以直接抄走的原地修改实现以及我在本地调样例时踩过的几个坑。无论你是刚开始刷矩阵类题还是已经写过不少前缀和应该都能从里面找到一点用得上的东西。1. 题目读完先别急着枚举那个“包含左上角”才是重点1.1 题目到底在问什么原题的描述很简单给定一个m x n的整数矩阵grid和一个整数k返回“元素和小于等于k的子矩阵的数目”。但真正关键的后半句是这些子矩阵都必须包含矩阵最左上角的那个元素grid[0][0]。注意这里的“包含”不是“和左上角有交集”而是子矩阵作为一个矩形它的覆盖范围里必须带着(0,0)。因为子矩阵的定义是连续的行区间和列区间所以左上角(0,0)一旦被包含矩形的左边界只能是第0列上边界只能是第0行。换句话说任何一个合法子矩阵的形态都是固定的从(0,0)到某个(i, j)。这个结论非常关键。普通子矩阵计数需要我们枚举四个边界r1, c1, r2, c2四个变量两两组合复杂度直接起飞。但这里左边界和上边界都没得选只需要枚举右下角(i, j)。右下角定了子矩阵就定了总共只有m * n个候选。举个例子。假设矩阵是7 6 3 6 6 1k 18。所有以(0,0)为左上角的子矩阵其实就是下面这六个只有(0,0)和是7第一行前两个元素7 6 13第一行全部7 6 3 16左上角一个 2x1 的列7 6 13左上角 2x2 区域7 6 6 6 25整个 2x3 矩阵29统计一下小于等于18的是前四个所以答案就是4。1.2 为什么绝大多数人会在这里跑偏我刷题时有个习惯看到“子矩阵”三个字肌肉记忆就是“二维前缀和 四个循环枚举边界”。这种条件反射在遇到 3070 这种题时反而害人。我想很多人第一眼看到题目会直接把它理解成“统计所有子矩阵中元素和小于等于 k 的个数”。如果真这么理解那问题就变成了一道难度高得多的计数题。因为子矩阵可以任意取行区间、列区间你需要保证任何位置都可能成为左上角也要保证任何位置都能成为右下角。光是枚举边界就是O(m^2 n^2)数据规模稍微大一点就完全跑不动。更关键的是如果矩阵元素不是非负的连滑动窗口、双指针这类优化都用不上因为你不能利用“扩大矩形和一定变大”的单调性。这题能轻松做出来靠的就是“必须包含左上角”这个限制条件。所以我的第一个建议是拿到任何矩阵题先把题面里的限定词划出来。特别是“包含某个点”“从左上角出发”“只能向右向下走”这类描述往往直接把一道看起来很难的问题简化成了前缀和问题。1.3 为什么右下角定了矩形就定了可能有人会问包含(0,0)的矩形为什么不能是比如(0,0)到(1, 2)以外的形状因为在矩阵里一个子矩阵是由连续的行和列组成的。你想想如果这个矩形包含了一行0和一列0那它一定从第0行开始、从第0列开始不可能出现“从第 1 行开始但包含 (0,0)”这种情况因为一旦包含(0,0)子矩阵的左上角就已经被强制固定为(0,0)了。把这个逻辑再推一步既然左上角固定为(0,0)那么子矩阵的和就是矩阵从(0,0)到(i,j)这一整块矩形区域的和。这正是二维前缀和的定义。所以我们只要把每一个“前缀矩形”的和算出来再数一数哪些小于等于k就行。很多最优解都选择“原地修改”把输入的grid直接改造成“以 (0,0) 为左上角的前缀和矩阵”。这样做的好处是额外空间复杂度是O(1)不用新开一个同样大小的二维数组。理解了这一点后面的代码就顺理成章了。2. 二维前缀和公式三行递推但顺序绝不能写错2.1 前缀和的定义与递推先明确一下符号。设原始矩阵是a我们想得到一个矩阵S其中S[i][j] 从 (0,0) 到 (i,j) 这个矩形内所有元素的和那S[i][j]应该怎么由小规模结果推导出来你可以把(0,0)到(i,j)这个矩形拆成三块蓝色部分(0,0)到(i-1, j)也就是“上面不含当前行的矩形”。绿色部分(0,0)到(i, j-1)也就是“左边不含当前列的矩形”。右下角单独的那个格子a[i][j]。但如果你直接加蓝色和绿色会重叠一块区域(0,0)到(i-1, j-1)。所以要用容斥原理把这块重叠减掉一次。于是得到最经典的递推公式S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]生活化一点理解你想算“全班同学的总分”可以先算“上一排同学的总分”再算“左边所有同学的总分”两者相加时左上角那批同学被重复算了一次所以要减去一次最后再加上当前这个同学自己的分数。这个公式就是二维前缀和思想的基石后面所有代码都是它的变体。2.2 原地修改为什么可行如果新开一个dp数组逻辑最安全dp[i][j]存前缀和a保持原始值不动。但题目标题里明确写了“原地修改”意思是我们直接复用输入的grid作为前缀和矩阵不再额外分配m * n的空间。为什么可以原地因为计算S[i][j]时只依赖三个位置上方S[i-1][j] 左方S[i][j-1] 左上S[i-1][j-1]只要保证遍历顺序是“从上到下、从左到右”那么当程序执行到(i,j)时这三个位置都已经被更新成前缀和了。换句话说grid[i-1][j]、grid[i][j-1]、grid[i-1][j-1]都已经是处理完的S值可以直接读。所以原地修改的代码可以写得很短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] # 减左上重叠这里有个地方很容易绕晕执行grid[i][j] grid[i-1][j]时grid[i-1][j]已经被上一轮的循环改写成前缀和了不是原始数组里的值。这正是我们想要的。千万别在脑子里把grid还当成原始矩阵不然 Debug 半天都找不出问题。2.3 边界条件的三件套边界条件主要有三种情况i 0, j 0左上角第一个格子没有任何东西可以加grid[0][0]本身就是前缀和。i 0, j 0只能加左方的值不能加上方也不能减左上。i 0, j 0只能加上方的值不能加左方也不能减左上。我写的三个if条件刚好覆盖这三种情况。这也是最容易出错的地方。如果你不想每次写一堆if另一个常见做法是开一个(m1) x (n1)的dp数组把第0行、第0列全部留成0然后从1开始遍历dp [[0] * (n 1) for _ in range(m 1)] for i in range(m): for j in range(n): dp[i1][j1] grid[i][j] dp[i][j1] dp[i1][j] - dp[i][j]这样就不用写任何边界判断因为dp[i][0]和dp[0][j]都是0公式自动成立。缺点是多花了O(mn)的空间。两种写法都正确但既然标题强调“原地修改”我会重点讲第一种。3. 答案就藏在同一趟循环里完整代码与手算验证3.1 计数逻辑的等价性很多人改完前缀和矩阵之后会习惯性地再单独开一遍双层循环去数答案。其实完全没必要。因为每个grid[i][j]经过原地修改后代表的就是从(0,0)到(i,j)的唯一一个合法子矩阵的和。我们遍历grid的每一个格子本来就要完整走一遍m * n个位置既然每到一个位置都已经知道它的前缀和了那顺手判断它是否小于等于k然后累加答案就是自然而然的事情。也就是说这题的答案就是统计所有满足 grid[i][j] k 的格子个数但要注意这里必须用修改后的grid[i][j]而不是原始grid[i][j]。如果你在循环里先判断原始值、再做前缀和那结果就完全错了。3.2 可以直接抄的 Python 与 C 实现Python 版本from typing import List 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 ansC 版本class Solution { public: int countSubmatrices(vectorvectorint grid, int k) { int m grid.size(), n grid[0].size(); int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0) grid[i][j] grid[i - 1][j]; if (j 0) grid[i][j] grid[i][j - 1]; if (i 0 j 0) grid[i][j] - grid[i - 1][j - 1]; if (grid[i][j] k) ans; } } return ans; } };核心逻辑只有三行加上方、加左方、减左上。接着一个if判断计数。整段代码的时间复杂度是O(mn)额外空间是O(1)因为修改都是在原数组上完成的。3.3 用一个 2 行 3 列的矩阵全程手算光看代码不够我习惯拿一组小数据从零手算一遍。假设输入grid [[1, 2, 3], [4, 5, 6]] k 10开始原地遍历。i0, j0grid[0][0] 1作为第一个前缀和答案ans 1。i0, j1grid[0][1] 2 grid[0][0] 3这个3是12的结果小于10ans 2。i0, j2grid[0][2] 3 grid[0][1] 6这是123的和小于10ans 3。i1, j0grid[1][0] 4 grid[0][0] 5这是14的和小于10ans 4。i1, j1grid[1][1] 5 grid[0][1] grid[1][0] - grid[0][0] 5 3 5 - 1 12大于10不计入。i1, j2grid[1][2] 6 grid[0][2] grid[1][1] - grid[0][1] 6 6 12 - 3 21大于10不计入。最终答案4。手动检查一下合法子矩阵[1]、[1,2]、[1,2,3]、[[1],[4]]刚好四个。和代码跑出来的结果一致。4. 原地修改 vs 另开数组四个高频踩坑与排查清单4.1 坑位对照表我把这一类题容易踩的坑整理成了一张表每次写前缀和之前扫一眼能省下不少调试时间。坑位现象原因解决办法看漏“包含左上角”条件跑去枚举所有子矩阵超时或 TLE把问题复杂度想高了读题阶段把限定词划线确认左上角固定原地修改时误读原始值结果整体偏大或偏小修改后grid[i-1][j]已是前缀和不是原始a[i-1][j]明确写注释当前矩阵被改造成前缀和矩阵边界条件写错首行、首列出错i0或j0时不该减左上角用if判断或用(m1)x(n1)偏移数组数据类型溢出计数错误甚至负数前缀和累加超过 int 范围后溢出根据题目数据范围选择long long或 Python第一个坑最隐蔽。我见过不少讨论区里的解法直接用四层循环枚举任意子矩阵结果发现题目限制一个m,n 1000就直接傻眼。其实题目本身的数据范围并不大但一旦误读条件复杂度就会从O(mn)变成O(m^2 n^2)完全不是一个量级。4.2 关于溢出与数据类型二维前缀和在累加过程中值可能远远超过原始矩阵里单个元素的范围。假设m n 1000每个格子1000整个矩阵总和就是10^9。如果题目还允许更大的值前缀和很容易超过int的表示范围。在 Python 里这不是问题因为整数可以无限扩大。但在 C 或 Java 里就要留意。如果你用int grid[][]做原地修改而题目数据又恰好把前缀和顶到2^31 - 1以上那结果会溢出成负数后面所有判断都会出错。解决办法有两个如果确定前缀和不会超过 int 范围原地修改是安全的。如果不确定建议另开一个long long类型的二维数组存前缀和不要强行原地修改。这里多说一句在面试里“原地修改”确实能展示你对空间复杂度的敏感但它不是万能的。如果为了原地修改导致数据溢出那还不如多花一点内存换正确性。工程上正确性永远排在省内存前面。4.3 如果题目不允许修改输入怎么办有些场景下输入数组是只读的或者后续还要用原始矩阵这时候就不能原地修改。那最简单的做法是使用带偏移的二维前缀和数组。代码可以写成这样m, n len(grid), len(grid[0]) dp [[0] * (n 1) for _ in range(m 1)] ans 0 for i in range(m): for j in range(n): dp[i 1][j 1] grid[i][j] dp[i][j 1] dp[i 1][j] - dp[i][j] if dp[i 1][j 1] k: ans 1 return ans这种写法的好处是边界判断完全消失代码更像公式本身。缺点是额外空间是O(mn)。在实际竞赛或面试中我更推荐这个版本因为它正确性更高代码也更不容易写错。只有在明确要求原地修改时才去省那部分空间。5. 一个题背后的通用前缀和思维以后遇到别只知道套公式5.1 一维前缀和与二维前缀和的家族关系很多人把前缀和当成一个“背公式”的工具一维就是pre[i] pre[i-1] a[i]二维就是“加上方加左方减左上”。但公式背后的思想是一致的用空间换时间把频繁区间求和变成O(1)查询。一维前缀和解决的是“连续子数组的和”二维前缀和解决的是“连续子矩阵的和”。如果题目问的是“只包含左上角的前缀矩形”那就退化成O(1)判断如果问的是“任意子矩阵”那就要结合枚举边界、压缩数组等手段。以后再遇到类似的矩阵题可以先问自己三个问题子矩阵的左上角是不是固定矩阵元素是不是非负单调性能不能用题目要的是最大、最小、数量还是一个具体区域这三个问题的答案基本就能决定你能不能向前缀和方向走。5.2 如果去掉“包含左上角”问题会变得多难有朋友可能会好奇如果题目改成“统计所有元素和小于等于 k 的子矩阵”还能这样做吗答案是不能。那就得换思路了。一个比较经典的优化是枚举子矩阵的上边界和下边界把每一列在这个行区间内的和压缩成一个一维数组于是问题变成“一维数组里有多少个连续子数组的和小于等于 k”。如果矩阵元素非负一维部分可以用双指针滑动窗口做到O(n)整体复杂度O(m^2 n)。思路大致是这样外层循环枚举上边界top。内层循环枚举下边界bottom。用一个数组colSum累加每一列从top到bottom的纵向和。在colSum上跑双指针统计以每个right结尾且和不超过k的左边界数量。这个题如果再加上“矩阵元素可以是负数”那难度又会跳一档因为单调性没了滑动窗口不再适用只能配合前缀和加有序表或平衡树来做。你看同一个题干删掉一个限定条件难度就能从简单题跳到中等偏难。这也是为什么我一直强调读题要细致。5.3 我在刷题时养成的三个习惯最后分享几个我实际做题时觉得很好用的习惯。可能不是标准教程但对提高一次通过率很有帮助。第一个习惯动手写代码之前先用一个很小的矩阵手工算一遍答案。比如 2x2 或 2x3 的矩阵把每一步前缀和都写在纸上。这样能逼着自己把公式和边界彻底想清楚而不是上来就套模板。第二个习惯如果允许额外空间我优先选偏移数组而不是原地修改。偏移数组dp[m1][n1]虽然在空间上多占一点但边界判断少很多代码几乎不会因为i-1越界报错。等到时间充裕再思考能否优化成原地修改。第三个习惯每一道矩阵前缀和题我都会顺手考虑“如果左上角不固定我该怎么改”。这样不是为了自找麻烦而是因为很多实际业务里的图像积分图、区域统计、窗口和计算本质上都是前缀和的应用。你多推一层下次遇到变体题就不慌了。这道 3070 虽然难度不算高但它的价值在于提醒我们子矩阵不一定都要枚举四个角前缀和也不一定非要重新开数组。把“左上角锁死”这个条件利用起来原地修改一趟扫完既简洁又高效。以后在讨论区看到有人问“为什么这题能原地修改”我大概也能很自然地回答因为每个右下角都唯一对应一个合法子矩阵改完直接数格子就行了。