我最早看到力扣 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，另一个常见做法是开一个(m+1) x (n+1)的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[i+1][j+1] = grid[i][j] + dp[i][j+1] + dp[i+1][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(vector<vector<int>>& 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开始原地遍历。
i=0, j=0：grid[0][0] = 1，作为第一个前缀和，答案ans = 1。
i=0, j=1：grid[0][1] = 2 + grid[0][0] = 3，这个3是1+2的结果，小于10，ans = 2。
i=0, j=2：grid[0][2] = 3 + grid[0][1] = 6，这是1+2+3的和，小于10，ans = 3。
i=1, j=0：grid[1][0] = 4 + grid[0][0] = 5，这是1+4的和，小于10，ans = 4。
i=1, j=1：grid[1][1] = 5 + grid[0][1] + grid[1][0] - grid[0][0] = 5 + 3 + 5 - 1 = 12，大于10，不计入。
i=1, j=2：grid[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] | 明确写注释：当前矩阵被改造成前缀和矩阵 |
| 边界条件写错 | 首行、首列出错 | i=0或j=0时不该减左上角 | 用if判断，或用(m+1)x(n+1)偏移数组 |
| 数据类型溢出 | 计数错误，甚至负数 | 前缀和累加超过 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[m+1][n+1]虽然在空间上多占一点，但边界判断少很多，代码几乎不会因为i-1越界报错。等到时间充裕，再思考能否优化成原地修改。
第三个习惯：每一道矩阵前缀和题，我都会顺手考虑“如果左上角不固定，我该怎么改”。这样不是为了自找麻烦，而是因为很多实际业务里的图像积分图、区域统计、窗口和计算，本质上都是前缀和的应用。你多推一层，下次遇到变体题就不慌了。
这道 3070 虽然难度不算高，但它的价值在于提醒我们：子矩阵不一定都要枚举四个角，前缀和也不一定非要重新开数组。把“左上角锁死”这个条件利用起来，原地修改一趟扫完，既简洁又高效。以后在讨论区看到有人问“为什么这题能原地修改”，我大概也能很自然地回答：因为每个右下角都唯一对应一个合法子矩阵，改完直接数格子就行了。
与SIGPIPE信号导致进程崩溃的排查与修复)
