1. 题目到底在问什么1.1 题面拆解与答案规模估算LeetCode 3070 这道题我愿称之为“二维前缀和基本功的最佳练手题”。题面很干净给你一个 m×n 的整数矩阵 grid 和一个整数 k要求返回矩阵中元素和小于等于 k 的子矩阵数量。子矩阵指任意连续行区间和连续列区间围出来的矩形单个格子也算整行整列也算。先别急着写代码我习惯先估算一下答案的极端规模。一个 m×n 的矩阵所有子矩阵的数量是 [m(m1)/2] × [n(n1)/2]。如果 mn100这个数约等于 5050×5050也就是 25,502,500两千五百万出头。这个规模下用 long long 统计答案完全不会溢出最终返回 int 也安全。但你要是有朝一日遇到 m、n 都是 1000 的同型问题这个数字会膨胀到几千亿级别那时候就不得不考虑取模或者换统计方式了。题目里 grid 的元素是非负整数这一点很关键。正因为非负子矩阵的和才具备单调性——矩形扩大只会让和不减。这个性质在后面优化时会派上大用场。如果你在别的平台看到类似题目但没有说明非负那优化思路就要重新评估不能无脑套双指针。1.2 从暴力到前缀和的思维路径最早接触这类题很多人第一反应是四层循环枚举左上角和右下角然后对矩形内部再做两层循环求和。这样就是 O(m^3 n^3) 的复杂度100×100 的矩阵就直接跑不动了。所以第一步优化一定是预处理把“求任意矩形和”这件事变成 O(1) 查询。这就是二维前缀和。二维前缀和本身并不复杂它是一维前缀和的自然扩展。一维前缀和 s[i] 表示前 i 个元素的和二维前缀和 pre[i][j] 表示从 (0,0) 到 (i,j) 这个左上角矩形区域内的所有元素和。一旦预处理完任意子矩阵 (r1,c1) 到 (r2,c2) 的和就能通过容斥公式算出来。代价是 O(mn) 的预处理时间换来 O(1) 的查询而子矩阵数量本身是 O(m^2 n^2)所以整体复杂度降到了 O(m^2 n^2)。这里有个容易被忽略的点很多人以为“前缀和”必须开一个新的二维数组其实完全可以原地改 grid。标题里的“原地修改”就是这个意思。它的价值不只是省那几 MB 内存更是一种代码风格的体现——递归思想、滚动数组、空间复用这些技巧本质上都是同一类思维能用已有空间就不开新空间。1.3 数据范围和隐藏细节虽然题目保证 grid 非空但写代码时我依然会习惯性加一行防御判断。工程上这叫“防御式编程”LeetCode 上用不上但面试手写代码时面试官会觉得你考虑问题周全。另外如果 k 非常小比如小于 0由于元素非负答案自然就是 0。你可以不特判因为代码里的统计条件会自动过滤掉所有不满足的子矩阵但如果想省时间提前判断 k 0 直接返回 0 也完全合理。还有一个隐藏细节k 的范围可能很大前缀和数组里存的值也可能超出 int 范围。比如每格数值 10000100×100 的矩阵最大前缀和就是 1 亿还没爆 int。可一旦数据范围放宽到更大规模或数值上调你就会突然遇到溢出导致的错误答案。所以我的习惯是所有求和用 long long 算返回再转 int。宁可多写一个强转也不要等溢出后抓耳挠腮。2. 二维前缀和的容斥原理与原地修改2.1 前缀和公式是怎么来的先看一维的情况。数组 a 的前缀和数组 s 满足 s[i] s[i-1] a[i]。二维前缀和 pre[i][j] 的含义是“从 (0,0) 到 (i,j) 的矩形和”。那 pre[i][j] 能不能用几个相邻格子算出来当然可以pre[i][j] a[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1]为什么是加两个减一个因为 pre[i-1][j] 覆盖了上面那块区域pre[i][j-1] 覆盖了左边那块区域它们重叠的部分恰好是 pre[i-1][j-1]也就是左上角那块。两块区域相加时重叠区域被算了两次所以要扣掉一次最后再加上当前位置的原始值 a[i][j]。这个容斥思想跟集合求并集的大小一模一样|A∪B| |A| |B| - |A∩B|。理解了这层类比公式就不需要死记硬背。查询任意子矩阵和时同样是容斥sum(r1,c1,r2,c2) pre[r2][c2] - pre[r1-1][c2] - pre[r2][c1-1] pre[r1-1][c1-1]大矩形减去上方多出来的条、再减去左方多出来的条结果左上角那块被减了两次需要再加回来一次。整个过程就是“大减小、加交集”。2.2 原地修改为什么安全开一个新数组存 pre 是最稳妥的写法但题目既然点名“原地修改”我们就要搞清楚原地改到底可不可行。答案是可前提是你按行主序遍历矩阵也就是外层循环按 i内层循环按 j从左到右、从上到下。为什么行主序就安全因为处理到 (i,j) 时当前格子存的值还是原始值还没被动过而它依赖的三个格子 (i-1,j)、(i,j-1)、(i-1,j-1) 都已经被处理完了它们当前存的值已经是对应区域的前缀和。也就是说依赖项都是“已完成的产物”当前项是“未加工的原料”整个操作就像流水线前一步的产出恰好是后一步的输入。这正是原地算法的核心逻辑不额外申请数组把矩阵本身当作滚动工作区。代价是原始矩阵会被覆盖如果后面还要用原值就必须提前备份。这也是为什么不少人会在写完原地前缀和后后面做优化时发现 grid[i][j] 已经不是原始 grid[i][j] 了进而踩坑。2.3 两种写法的差异原地构建前缀和有两种写法。第一种用临时变量更接近推导公式可读性最好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; } }第二种直接就地累加代码更短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]; } }两种写法结果完全一致。第二种看起来有点吓人因为它连续修改了 grid[i][j] 三次但每一步都符合公式。我个人的建议是笔试或面试时写第一种因为考官能一眼看出你的思路刷题提交不希望被运行时间折磨时两种都没区别。关键是你要理解为什么可以这样改别只是背代码。3. 可提交的完整实现与逐段讲解3.1 C 版题解class Solution { public: int countSubmatrices(vectorvectorint grid, int k) { if (grid.empty() || grid[0].empty()) return 0; int m grid.size(), n grid[0].size(); // 原地构建二维前缀和 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; } } auto rectSum [](int r1, int c1, int r2, int c2) - long long { long long res grid[r2][c2]; if (r1 0) res - grid[r1-1][c2]; if (c1 0) res - grid[r2][c1-1]; if (r1 0 c1 0) res grid[r1-1][c1-1]; return res; }; long long ans 0; for (int r1 0; r1 m; r1) { for (int c1 0; c1 n; c1) { for (int r2 r1; r2 m; r2) { for (int c2 c1; c2 n; c2) { if (rectSum(r1, c1, r2, c2) k) { ans; } } } } } return (int)ans; } };这里 rectSum 用 lambda 封装内部做了 4 种边界情况的判断。最值得学习的点是r1 为 0 时不能减 grid[-1][c2]c1 为 0 时不能减 grid[r2][-1]只有在 r1 和 c1 同时大于 0 时才需要加回 grid[r1-1][c1-1]。边界条件多容易写错封装成函数能有效降低出错率。3.2 Python 版题解与性能优化from typing import List class Solution: def countSubmatrices(self, grid: List[List[int]], k: int) - int: m, n len(grid), len(grid[0]) for i in range(m): for j in range(n): cur grid[i][j] if i 0: cur grid[i-1][j] if j 0: cur grid[i][j-1] if i 0 and j 0: cur - grid[i-1][j-1] grid[i][j] cur ans 0 for r1 in range(m): for c1 in range(n): for r2 in range(r1, m): for c2 in range(c1, n): s grid[r2][c2] if r1 0: s - grid[r1-1][c2] if c1 0: s - grid[r2][c1-1] if r1 0 and c1 0: s grid[r1-1][c1-1] if s k: ans 1 return ans相比于 C 版Python 版我没有把矩形求和抽成函数而是直接把边界判断内联到四层循环里。为什么因为 Python 的函数调用开销比 C 大得多2500 万次函数调用会慢到不可接受。内联判断虽然代码重复但能省下大量时间。这就是不同语言之间同样的算法需要做不同工程取舍的典型例子。Python 在 100×100 规模下四层循环大约 2500 万次实际上是可以跑完的但时间可能接近极限。如果你觉得不稳还可以做个小优化固定 r1 和 c1 后一旦 r2、c2 组成的子矩阵和大于 k后面的更大子矩阵肯定也不满足因为元素非负可以提前 break。不过要注意这个优化依赖非负性质。3.3 边界条件归纳我把矩形求和的四种情况列成一张表方便对照r1 是否为 0c1 是否为 0子矩阵和公式是是grid[r2][c2]是否grid[r2][c2] - grid[r2][c1-1]否是grid[r2][c2] - grid[r1-1][c2]否否grid[r2][c2] - grid[r1-1][c2] - grid[r2][c1-1] grid[r1-1][c1-1]这套边界判断在之后很多二维前缀和的题目里都会重复出现。与其每次都现推不如直接记下这个套路。我看过不少同学在 max sum submatrix、range sum query 2D 这类题里反复踩同样的边界坑本质上都是因为没有把这四种情况系统整理过。4. 从 O(m^2 n^2) 再进一步固定行边界 列滑窗4.1 利用非负性质压缩枚举维度四层循环的 O(m^2 n^2) 在 100 规模下完全没问题但如果你追求更优的复杂度可以利用题目中“grid 元素非负”这条性质。思路是枚举子矩阵的上下边界 r1、r2然后把上下边界之间的每一列元素和求出来得到数组 col[j]。接下来问题就变成在一维数组 col 上有多少个连续子数组的和小于等于 k并且这个子数组的左端点 c1、右端点 c2 天然满足 c1 ≤ c2。因为 col[j] 非负所以右端点向右移动时窗口和只增不减。用双指针维护窗口即可。整体流程枚举上边界 r1。维护一个长度为 n 的数组 col初始全 0。枚举下边界 r2 从 r1 到 m-1把原始矩阵第 r2 行的值累加到 col。在 col 上做双指针统计右指针扩展窗口和首次超过 k 时收缩左指针每次统计当前窗口长度。这个做法的复杂度是 O(m^2 n)。从 O(m^2 n^2) 到 O(m^2 n)本质上是把“枚举左右边界”变成了“滑动窗口一次扫完”省掉了一个 n 维度。代价是需要 O(n) 的辅助数组。有一个绕不开的前提这个优化必须使用原始矩阵的值。如果你在前面已经做了原地二维前缀和grid 里存的就不再是原值col 的累加结果就是错的。所以这里只能二选一要么直接对原始矩阵做这个 O(m^2 n) 算法要么在构建原地前缀和之前先把原始矩阵复制到另一个数组备用。我自己刷题时通常先写完二维前缀和版本并确保通过再考虑是否需要优化版本。因为 O(m^2 n^2) 对这个数据范围已经够用优化版本虽然复杂度更好但写起来更容易出错尤其是边界和指针移动的细节。4.2 三种方案复杂度对比方案预处理子矩阵查询整体复杂度额外空间暴力枚举无O(mn)O(m^3 n^3)O(1)原地二维前缀和 四层枚举O(mn)O(1)O(m^2 n^2)O(1)固定行边界 列滑窗无O(n)O(m^2 n)O(n)通常面试官不会逼你写出第三种第二种已经能体现前缀和思维和空间优化意识。第三种更像是展示你理解“非负条件下的单调性”可以作为加分项提一嘴但不必作为主选。4.3 题目变形从“小于等于 k”到“恰好等于 k”如果把题改成统计元素和“恰好等于 k”的子矩阵数量答案就完全不同了。这时非负性质依然可以帮助我们滑动窗口但统计方式需要变窗口和不超过 k 时移动右指针超过 k 时移动左指针刚好等于 k 时记录答案然后继续移动左指针寻找下一个可能的窗口。不过“恰好等于 k”这个变体在二维矩阵上还会遇到一个经典坑子矩阵内部可能包含值为 0 的元素导致和为 k 的窗口长度不唯一。比如窗口和已经等于 k继续扩展右端点时如果遇到 0那么新窗口的和依然等于 k这也算新的子矩阵。如果忽略 0 元素就会漏解。这种情况下更稳妥的做法是用哈希表配合前缀和或者对每一对行边界跑一维“和为 k 的子数组”算法。这就是从一个基础题延伸出去的另一个知识面了等你把 3070 吃透之后再去碰也不迟。5. 易错点与调试经验实录5.1 我在刷这道题时踩过的坑第一个坑就是前缀和溢出。早期我图省事子矩阵求和全用 int结果在数据范围较大的测试用例里直接算出负数。后来养成习惯涉及累加一律 long long只在最后返回时转回 int。第二个坑是边界判断。写 rectSum 时一开始没考虑 r1 或 c1 等于 0 的情况程序直接越界崩溃。这提醒我一个很重要的刷题习惯四层大循环之前先画一个 2×2 的小矩阵手算一遍边界值再对照代码看是否正确。第三个坑是枚举范围写错。子矩阵必须满足 r2 ≥ r1、c2 ≥ c1但有些人会把 r2 从 0 开始循环导致 r2 r1 的“倒置矩阵”也被统计进去。虽然求和公式对倒置矩阵没有定义但代码可能会给出一个看起来“合理”的错误数值这种 bug 特别隐蔽不仔细对拍根本发现不了。第四个坑和原地修改有关。我一开始把二维前缀和构建完然后想顺手在同一个 grid 上做滑窗优化结果 col 累加的数据全不对。排查半天才意识到原始矩阵已经被前缀和覆盖。这个经历也让我总结出一条经验一旦决定原地修改就要想清楚后续步骤是否还依赖原始数据。5.2 快速自测与对拍技巧遇到这种矩阵题我强烈建议写一个超级简朴的暴力版作为对照def brute(grid, k): m, n len(grid), len(grid[0]) ans 0 for r1 in range(m): for c1 in range(n): for r2 in range(r1, m): for c2 in range(c1, n): s 0 for i in range(r1, r21): for j in range(c1, c21): s grid[i][j] if s k: ans 1 return ans这个暴力版复杂度极高但逻辑绝对朴实适合做正确性基准。我每次写完优化解法都会用几个小矩阵把两个版本跑一遍随机生成 5×5、8×8 的矩阵比对结果。对拍通过之后再拿大用例测性能。这个过程能帮你找出绝大多数边界和逻辑 bug。如果你没有现成的对拍脚本一个变通办法是手动构造几个特殊矩阵全 0 矩阵、全 1 矩阵、单行矩阵、单列矩阵、元素对角线很大的矩阵。把这几类都跑一遍基本能覆盖 80% 的边界问题。5.3 面试答题的节奏建议这道题如果出现在面试场景我建议这样组织回答先口述暴力思路明确指出复杂度瓶颈。然后引出二维前缀和解释容斥公式时用“集合交并”帮助面试官理解。再强调代码里采用原地修改空间复杂度 O(1)。最后如果面试官追问可以补充一句“由于本题元素非负用固定行边界加滑动窗口可以再降一个数量级”简单讲讲原理即可。整个过程既有递进感又不会一股脑倒出太多信息。我在模拟面试时见过一种典型尝试学生一上来就背出 O(m^2 n) 的滑窗写法结果边界处理不熟练卡了半天。反而是老老实实写二维前缀和的同学很快就把代码跑通。所以不要盲目追求最优解稳妥地把基础解法写对本身就是一个很强的能力。6. 最后的个人体会刷题这件事很多人强调“数量”但我觉得更重要的是“沉淀”。3070 这道题真正值得内化的不是那 20 行代码而是容斥公式、边界处理、空间复用这三个元技能。之后再遇到二维区域求和类问题你不需要重新想直接调用这套思维模型就行。我自己的习惯是每刷完一道矩阵题就手动在白板上把“原地前缀和”的流程画一遍标注每个依赖格子的状态。画过两三次之后这套逻辑就成了肌肉记忆写起来完全不需要犹豫。另外如果你准备把这道题写进题解或项目笔记建议在代码注释里把边界判断写清楚。因为这类代码细节多三个月后回来看如果不依赖注释你可能又得对着四种情况推半天。注释不是写给读者看的更多时候是写给未来的自己。最终送上八个字先求正确再谈优化。408 行的算法世界从来不缺花哨解法但能把最朴素的前缀和写对、写稳已经胜过很多人了。 
长河君 · 2026/10/13 15:44:39 · 阅读 1.2k 二维前缀与原地修改：LeetCode 3070 子矩阵计数方法
1. 题目到底在问什么1.1 题面拆解与答案规模估算LeetCode 3070 这道题我愿称之为“二维前缀和基本功的最佳练手题”。题面很干净给你一个 m×n 的整数矩阵 grid 和一个整数 k要求返回矩阵中元素和小于等于 k 的子矩阵数量。子矩阵指任意连续行区间和连续列区间围出来的矩形单个格子也算整行整列也算。先别急着写代码我习惯先估算一下答案的极端规模。一个 m×n 的矩阵所有子矩阵的数量是 [m(m1)/2] × [n(n1)/2]。如果 mn100这个数约等于 5050×5050也就是 25,502,500两千五百万出头。这个规模下用 long long 统计答案完全不会溢出最终返回 int 也安全。但你要是有朝一日遇到 m、n 都是 1000 的同型问题这个数字会膨胀到几千亿级别那时候就不得不考虑取模或者换统计方式了。题目里 grid 的元素是非负整数这一点很关键。正因为非负子矩阵的和才具备单调性——矩形扩大只会让和不减。这个性质在后面优化时会派上大用场。如果你在别的平台看到类似题目但没有说明非负那优化思路就要重新评估不能无脑套双指针。1.2 从暴力到前缀和的思维路径最早接触这类题很多人第一反应是四层循环枚举左上角和右下角然后对矩形内部再做两层循环求和。这样就是 O(m^3 n^3) 的复杂度100×100 的矩阵就直接跑不动了。所以第一步优化一定是预处理把“求任意矩形和”这件事变成 O(1) 查询。这就是二维前缀和。二维前缀和本身并不复杂它是一维前缀和的自然扩展。一维前缀和 s[i] 表示前 i 个元素的和二维前缀和 pre[i][j] 表示从 (0,0) 到 (i,j) 这个左上角矩形区域内的所有元素和。一旦预处理完任意子矩阵 (r1,c1) 到 (r2,c2) 的和就能通过容斥公式算出来。代价是 O(mn) 的预处理时间换来 O(1) 的查询而子矩阵数量本身是 O(m^2 n^2)所以整体复杂度降到了 O(m^2 n^2)。这里有个容易被忽略的点很多人以为“前缀和”必须开一个新的二维数组其实完全可以原地改 grid。标题里的“原地修改”就是这个意思。它的价值不只是省那几 MB 内存更是一种代码风格的体现——递归思想、滚动数组、空间复用这些技巧本质上都是同一类思维能用已有空间就不开新空间。1.3 数据范围和隐藏细节虽然题目保证 grid 非空但写代码时我依然会习惯性加一行防御判断。工程上这叫“防御式编程”LeetCode 上用不上但面试手写代码时面试官会觉得你考虑问题周全。另外如果 k 非常小比如小于 0由于元素非负答案自然就是 0。你可以不特判因为代码里的统计条件会自动过滤掉所有不满足的子矩阵但如果想省时间提前判断 k 0 直接返回 0 也完全合理。还有一个隐藏细节k 的范围可能很大前缀和数组里存的值也可能超出 int 范围。比如每格数值 10000100×100 的矩阵最大前缀和就是 1 亿还没爆 int。可一旦数据范围放宽到更大规模或数值上调你就会突然遇到溢出导致的错误答案。所以我的习惯是所有求和用 long long 算返回再转 int。宁可多写一个强转也不要等溢出后抓耳挠腮。2. 二维前缀和的容斥原理与原地修改2.1 前缀和公式是怎么来的先看一维的情况。数组 a 的前缀和数组 s 满足 s[i] s[i-1] a[i]。二维前缀和 pre[i][j] 的含义是“从 (0,0) 到 (i,j) 的矩形和”。那 pre[i][j] 能不能用几个相邻格子算出来当然可以pre[i][j] a[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1]为什么是加两个减一个因为 pre[i-1][j] 覆盖了上面那块区域pre[i][j-1] 覆盖了左边那块区域它们重叠的部分恰好是 pre[i-1][j-1]也就是左上角那块。两块区域相加时重叠区域被算了两次所以要扣掉一次最后再加上当前位置的原始值 a[i][j]。这个容斥思想跟集合求并集的大小一模一样|A∪B| |A| |B| - |A∩B|。理解了这层类比公式就不需要死记硬背。查询任意子矩阵和时同样是容斥sum(r1,c1,r2,c2) pre[r2][c2] - pre[r1-1][c2] - pre[r2][c1-1] pre[r1-1][c1-1]大矩形减去上方多出来的条、再减去左方多出来的条结果左上角那块被减了两次需要再加回来一次。整个过程就是“大减小、加交集”。2.2 原地修改为什么安全开一个新数组存 pre 是最稳妥的写法但题目既然点名“原地修改”我们就要搞清楚原地改到底可不可行。答案是可前提是你按行主序遍历矩阵也就是外层循环按 i内层循环按 j从左到右、从上到下。为什么行主序就安全因为处理到 (i,j) 时当前格子存的值还是原始值还没被动过而它依赖的三个格子 (i-1,j)、(i,j-1)、(i-1,j-1) 都已经被处理完了它们当前存的值已经是对应区域的前缀和。也就是说依赖项都是“已完成的产物”当前项是“未加工的原料”整个操作就像流水线前一步的产出恰好是后一步的输入。这正是原地算法的核心逻辑不额外申请数组把矩阵本身当作滚动工作区。代价是原始矩阵会被覆盖如果后面还要用原值就必须提前备份。这也是为什么不少人会在写完原地前缀和后后面做优化时发现 grid[i][j] 已经不是原始 grid[i][j] 了进而踩坑。2.3 两种写法的差异原地构建前缀和有两种写法。第一种用临时变量更接近推导公式可读性最好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; } }第二种直接就地累加代码更短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]; } }两种写法结果完全一致。第二种看起来有点吓人因为它连续修改了 grid[i][j] 三次但每一步都符合公式。我个人的建议是笔试或面试时写第一种因为考官能一眼看出你的思路刷题提交不希望被运行时间折磨时两种都没区别。关键是你要理解为什么可以这样改别只是背代码。3. 可提交的完整实现与逐段讲解3.1 C 版题解class Solution { public: int countSubmatrices(vectorvectorint grid, int k) { if (grid.empty() || grid[0].empty()) return 0; int m grid.size(), n grid[0].size(); // 原地构建二维前缀和 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; } } auto rectSum [](int r1, int c1, int r2, int c2) - long long { long long res grid[r2][c2]; if (r1 0) res - grid[r1-1][c2]; if (c1 0) res - grid[r2][c1-1]; if (r1 0 c1 0) res grid[r1-1][c1-1]; return res; }; long long ans 0; for (int r1 0; r1 m; r1) { for (int c1 0; c1 n; c1) { for (int r2 r1; r2 m; r2) { for (int c2 c1; c2 n; c2) { if (rectSum(r1, c1, r2, c2) k) { ans; } } } } } return (int)ans; } };这里 rectSum 用 lambda 封装内部做了 4 种边界情况的判断。最值得学习的点是r1 为 0 时不能减 grid[-1][c2]c1 为 0 时不能减 grid[r2][-1]只有在 r1 和 c1 同时大于 0 时才需要加回 grid[r1-1][c1-1]。边界条件多容易写错封装成函数能有效降低出错率。3.2 Python 版题解与性能优化from typing import List class Solution: def countSubmatrices(self, grid: List[List[int]], k: int) - int: m, n len(grid), len(grid[0]) for i in range(m): for j in range(n): cur grid[i][j] if i 0: cur grid[i-1][j] if j 0: cur grid[i][j-1] if i 0 and j 0: cur - grid[i-1][j-1] grid[i][j] cur ans 0 for r1 in range(m): for c1 in range(n): for r2 in range(r1, m): for c2 in range(c1, n): s grid[r2][c2] if r1 0: s - grid[r1-1][c2] if c1 0: s - grid[r2][c1-1] if r1 0 and c1 0: s grid[r1-1][c1-1] if s k: ans 1 return ans相比于 C 版Python 版我没有把矩形求和抽成函数而是直接把边界判断内联到四层循环里。为什么因为 Python 的函数调用开销比 C 大得多2500 万次函数调用会慢到不可接受。内联判断虽然代码重复但能省下大量时间。这就是不同语言之间同样的算法需要做不同工程取舍的典型例子。Python 在 100×100 规模下四层循环大约 2500 万次实际上是可以跑完的但时间可能接近极限。如果你觉得不稳还可以做个小优化固定 r1 和 c1 后一旦 r2、c2 组成的子矩阵和大于 k后面的更大子矩阵肯定也不满足因为元素非负可以提前 break。不过要注意这个优化依赖非负性质。3.3 边界条件归纳我把矩形求和的四种情况列成一张表方便对照r1 是否为 0c1 是否为 0子矩阵和公式是是grid[r2][c2]是否grid[r2][c2] - grid[r2][c1-1]否是grid[r2][c2] - grid[r1-1][c2]否否grid[r2][c2] - grid[r1-1][c2] - grid[r2][c1-1] grid[r1-1][c1-1]这套边界判断在之后很多二维前缀和的题目里都会重复出现。与其每次都现推不如直接记下这个套路。我看过不少同学在 max sum submatrix、range sum query 2D 这类题里反复踩同样的边界坑本质上都是因为没有把这四种情况系统整理过。4. 从 O(m^2 n^2) 再进一步固定行边界 列滑窗4.1 利用非负性质压缩枚举维度四层循环的 O(m^2 n^2) 在 100 规模下完全没问题但如果你追求更优的复杂度可以利用题目中“grid 元素非负”这条性质。思路是枚举子矩阵的上下边界 r1、r2然后把上下边界之间的每一列元素和求出来得到数组 col[j]。接下来问题就变成在一维数组 col 上有多少个连续子数组的和小于等于 k并且这个子数组的左端点 c1、右端点 c2 天然满足 c1 ≤ c2。因为 col[j] 非负所以右端点向右移动时窗口和只增不减。用双指针维护窗口即可。整体流程枚举上边界 r1。维护一个长度为 n 的数组 col初始全 0。枚举下边界 r2 从 r1 到 m-1把原始矩阵第 r2 行的值累加到 col。在 col 上做双指针统计右指针扩展窗口和首次超过 k 时收缩左指针每次统计当前窗口长度。这个做法的复杂度是 O(m^2 n)。从 O(m^2 n^2) 到 O(m^2 n)本质上是把“枚举左右边界”变成了“滑动窗口一次扫完”省掉了一个 n 维度。代价是需要 O(n) 的辅助数组。有一个绕不开的前提这个优化必须使用原始矩阵的值。如果你在前面已经做了原地二维前缀和grid 里存的就不再是原值col 的累加结果就是错的。所以这里只能二选一要么直接对原始矩阵做这个 O(m^2 n) 算法要么在构建原地前缀和之前先把原始矩阵复制到另一个数组备用。我自己刷题时通常先写完二维前缀和版本并确保通过再考虑是否需要优化版本。因为 O(m^2 n^2) 对这个数据范围已经够用优化版本虽然复杂度更好但写起来更容易出错尤其是边界和指针移动的细节。4.2 三种方案复杂度对比方案预处理子矩阵查询整体复杂度额外空间暴力枚举无O(mn)O(m^3 n^3)O(1)原地二维前缀和 四层枚举O(mn)O(1)O(m^2 n^2)O(1)固定行边界 列滑窗无O(n)O(m^2 n)O(n)通常面试官不会逼你写出第三种第二种已经能体现前缀和思维和空间优化意识。第三种更像是展示你理解“非负条件下的单调性”可以作为加分项提一嘴但不必作为主选。4.3 题目变形从“小于等于 k”到“恰好等于 k”如果把题改成统计元素和“恰好等于 k”的子矩阵数量答案就完全不同了。这时非负性质依然可以帮助我们滑动窗口但统计方式需要变窗口和不超过 k 时移动右指针超过 k 时移动左指针刚好等于 k 时记录答案然后继续移动左指针寻找下一个可能的窗口。不过“恰好等于 k”这个变体在二维矩阵上还会遇到一个经典坑子矩阵内部可能包含值为 0 的元素导致和为 k 的窗口长度不唯一。比如窗口和已经等于 k继续扩展右端点时如果遇到 0那么新窗口的和依然等于 k这也算新的子矩阵。如果忽略 0 元素就会漏解。这种情况下更稳妥的做法是用哈希表配合前缀和或者对每一对行边界跑一维“和为 k 的子数组”算法。这就是从一个基础题延伸出去的另一个知识面了等你把 3070 吃透之后再去碰也不迟。5. 易错点与调试经验实录5.1 我在刷这道题时踩过的坑第一个坑就是前缀和溢出。早期我图省事子矩阵求和全用 int结果在数据范围较大的测试用例里直接算出负数。后来养成习惯涉及累加一律 long long只在最后返回时转回 int。第二个坑是边界判断。写 rectSum 时一开始没考虑 r1 或 c1 等于 0 的情况程序直接越界崩溃。这提醒我一个很重要的刷题习惯四层大循环之前先画一个 2×2 的小矩阵手算一遍边界值再对照代码看是否正确。第三个坑是枚举范围写错。子矩阵必须满足 r2 ≥ r1、c2 ≥ c1但有些人会把 r2 从 0 开始循环导致 r2 r1 的“倒置矩阵”也被统计进去。虽然求和公式对倒置矩阵没有定义但代码可能会给出一个看起来“合理”的错误数值这种 bug 特别隐蔽不仔细对拍根本发现不了。第四个坑和原地修改有关。我一开始把二维前缀和构建完然后想顺手在同一个 grid 上做滑窗优化结果 col 累加的数据全不对。排查半天才意识到原始矩阵已经被前缀和覆盖。这个经历也让我总结出一条经验一旦决定原地修改就要想清楚后续步骤是否还依赖原始数据。5.2 快速自测与对拍技巧遇到这种矩阵题我强烈建议写一个超级简朴的暴力版作为对照def brute(grid, k): m, n len(grid), len(grid[0]) ans 0 for r1 in range(m): for c1 in range(n): for r2 in range(r1, m): for c2 in range(c1, n): s 0 for i in range(r1, r21): for j in range(c1, c21): s grid[i][j] if s k: ans 1 return ans这个暴力版复杂度极高但逻辑绝对朴实适合做正确性基准。我每次写完优化解法都会用几个小矩阵把两个版本跑一遍随机生成 5×5、8×8 的矩阵比对结果。对拍通过之后再拿大用例测性能。这个过程能帮你找出绝大多数边界和逻辑 bug。如果你没有现成的对拍脚本一个变通办法是手动构造几个特殊矩阵全 0 矩阵、全 1 矩阵、单行矩阵、单列矩阵、元素对角线很大的矩阵。把这几类都跑一遍基本能覆盖 80% 的边界问题。5.3 面试答题的节奏建议这道题如果出现在面试场景我建议这样组织回答先口述暴力思路明确指出复杂度瓶颈。然后引出二维前缀和解释容斥公式时用“集合交并”帮助面试官理解。再强调代码里采用原地修改空间复杂度 O(1)。最后如果面试官追问可以补充一句“由于本题元素非负用固定行边界加滑动窗口可以再降一个数量级”简单讲讲原理即可。整个过程既有递进感又不会一股脑倒出太多信息。我在模拟面试时见过一种典型尝试学生一上来就背出 O(m^2 n) 的滑窗写法结果边界处理不熟练卡了半天。反而是老老实实写二维前缀和的同学很快就把代码跑通。所以不要盲目追求最优解稳妥地把基础解法写对本身就是一个很强的能力。6. 最后的个人体会刷题这件事很多人强调“数量”但我觉得更重要的是“沉淀”。3070 这道题真正值得内化的不是那 20 行代码而是容斥公式、边界处理、空间复用这三个元技能。之后再遇到二维区域求和类问题你不需要重新想直接调用这套思维模型就行。我自己的习惯是每刷完一道矩阵题就手动在白板上把“原地前缀和”的流程画一遍标注每个依赖格子的状态。画过两三次之后这套逻辑就成了肌肉记忆写起来完全不需要犹豫。另外如果你准备把这道题写进题解或项目笔记建议在代码注释里把边界判断写清楚。因为这类代码细节多三个月后回来看如果不依赖注释你可能又得对着四种情况推半天。注释不是写给读者看的更多时候是写给未来的自己。最终送上八个字先求正确再谈优化。408 行的算法世界从来不缺花哨解法但能把最朴素的前缀和写对、写稳已经胜过很多人了。