1. 题目理解与整体设计思路
1.1 这题到底要我们干什么
先说题意吧。题目给了一个 m 行 n 列的矩阵 grid，我们要判断能不能用一条水平线和一条垂直线把整个矩阵切成四个非空的子矩阵，并且这四个子矩阵的元素和完全相等。能切出来就返回 true，切不出来就返回 false。
这题是系列题的第二版，第一版只让你判断能不能用一条水平线或者垂直线把矩阵一刀切成左右两块或上下两块，两块的和相等就行。到了 II，难度就从一维判断升级成了二维组合判断，需要在行方向和列方向同时找位置，四个角上的子矩阵都要满足相同的和。很多同学第一反应是“这题我会，枚举所有切法不就行了”，实际一写就发现，矩阵稍微大一点，暴力法的耗时直接受不了，真正麻烦的地方在于怎么把 O(m^2 * n^2) 的枚举降下来。
我当时刷这道题的时候，第一眼就锁定了两个关键词：前缀和、哈希表。前缀和负责 O(1) 拿任意子矩阵的和，哈希表负责把候选的行列位置快速筛出来。C++ 写这类题，代码本身并不长，但前缀和的边界、类型溢出、条件化简这些地方全是暗坑，今天这篇就把完整的推导和踩坑过程都捋一遍。
1.2 为什么第一反应是前缀和
题目里几乎所有操作都在问同一个问题：某个矩形区域的和是多少。比如左上角那块、右上角那块、左下角那块、右下角那块。如果你每次都是暴力去把范围内的所有元素加起来，光算一块就要 O(行数*列数)，再套上行列双重枚举，复杂度直接起飞。
这个时候前缀和就是标准答案。二维前缀和可以在 O(1) 时间内回答“从 (r1, c1) 到 (r2, c2) 这个子矩阵的和是多少”，查询一次只需要做几次加减法。刷 LeetCode 刷到矩阵题，凡是涉及到反复求某个区域的和，我的第一反应永远是前缀和。这不是什么玄学，就是这类题目的通用套路：预处理一次，查询任意次数，典型的空间换时间。
前缀和对这题的意义不只是查询快，它还能让整个判断条件变得非常干净。你不需要真的去“数”四块区域分别是多少，只需要拿前缀和数组里几个关键位置的值做比较，就能判断四个区域是否相等。后面环节我会详细推导，这是整道题的核心，也是从 I 到 II 最难想清楚的地方。
1.3 方案选型：暴力、前缀和、哈希表各有各的适用场景
先列出我能想到的三种方案，方便对比：
- 暴力法：枚举水平分割线的所有位置和垂直分割线的所有位置，每选定一对位置，就把四个子矩阵分别累加一遍。假设矩阵是 m 行 n 列，位置组合有 (m-1)(n-1) 种，每个位置计算四块和又要 O(mn)，总复杂度 O(m^2 * n^2)，m 和 n 只要到几百就完全没法跑。
- 纯前缀和 + 双重枚举：先用前缀和把每个子矩阵的和都变成 O(1) 查询，然后依然枚举所有水平线和垂直线的位置，总复杂度是 O(mn)，构建前缀和 O(mn)，枚举也是 O(m*n)。
- 前缀和 + 哈希表：在前一种方案的基础上，先用两个哈希集合记录满足“上半部分和是总和的 1/2”的行，以及满足“左半部分和是总和的 1/2”的列，最后只在候选行列里做检查，实际需要比较的位置数量会大幅减少。
我看到很多人纠结哈希表到底优化了什么，其实它并不是把最坏复杂度从 O(m*n) 变成 O(m+n)，因为最坏情况下候选行列依然可能很多。哈希表在这里的核心作用是让“哪些行列位置有资格成为分割线”这件事变得可以直接查询，代码语义也更清楚。数据量特别大、符合条件的行列很少的时候，收益会非常明显。所以实际写题时，我建议直接上第三种，稳。
2. 前置知识：二维前缀和的构建与O(1)区间查询
2.1 前缀和数组是怎么定义的
一维前缀和你们肯定都熟：pre[i] 表示原数组前 i 个元素的和。二维前缀和就是把这个概念推广到矩阵，pre[i][j] 表示从矩阵左上角 (0,0) 到 (i-1,j-1) 这个子矩阵的元素总和。注意我这里用的是“到 (i-1,j-1)”，也就是说 pre 的下标比原矩阵下标多 1，这是为了把边界情况都收进数组里，避免出现 i-1 为负数的情况。
构建的时候有一个固定公式，长这样：
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + grid[i-1][j-1]
这个公式用一句话解释就是：当前格子对应的大矩形和，等于“上面一块”加上“左边一块”，但红色部分的重叠区块被加了两次，所以要减掉一次，最后再加上当前格子自己的值。类比一下，就像你统计两个重叠矩形的覆盖面积，要减去重叠区域的面积，道理一样。
换成代码的话，可以先开一个 (m+1) 行 (n+1) 列的二维数组，全部初始化为 0，然后从第 1 行第 1 列开始双循环。这样做的唯一好处就是代码不用特判边界，统一的递推公式就能覆盖所有位置。
2.2 任意子矩阵的求和公式
有了 pre 数组之后，想要求出原矩阵中从 (r1, c1) 到 (r2, c2) 这个子矩阵的和，公式是：
sum = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]
同样用面积重叠的思路去理解：pre[r2+1][c2+1] 是左上角到右下角整个大块，先减掉上面多出来的部分 pre[r1][c2+1]，再减掉左边多出来的部分 pre[r2+1][c1]，左上角被减了两次的部分加回来 pre[r1][c1]。
这题里我们算四块区域的时候，会反复用这个公式，所以一定要把它刻在脑子里。很多新手写错前缀和题，基本都是在这个公式上出问题，比如忘记右下角坐标要加 1，或者加减号写反。
2.3 写前缀和时间损耗最小化的几个习惯
第一个习惯，数组类型一定要用 long long。LeetCode 矩阵题经常不声明数据范围，你看着 int 好像够用，实际上一列全是 1e9，来个 1000 行，前缀和轻松爆到 1e15，int 根本存不下。这个坑我踩过不止一次，所以现在一看到要算矩阵和，直接 long long 起步。
第二个习惯，pre 数组多开一行一列。我在前面已经说过，pre[i][j] 对应的是原矩阵到 (i-1,j-1) 的和，所以数组尺寸是 (m+1)(n+1)，一定不要开成 mn，否则边界位置全部越界。
第三个习惯，构建循环里注意 i 和 j 都是从 1 开始，遍历原矩阵元素时要用 grid[i-1][j-1]。这个很容易写顺手写错，一旦写错，调试起来又比较隐蔽，因为前几个值通常算出来还是对的，到后面才出问题。
3. 从“等和矩阵分割 I”到“II”：两个分割条件的推导
3.1 I 和 II 的差别到底在哪
第一版只需要找一条线，把矩阵切成上下两块或者左右两块，两块和相等。这个时候你只需要扫一遍每一行的行前缀和，遇到 pre[r][n] == total/2 就说明当前位置可以切，根本不需要考虑两条线交叉的问题。
到了 II，要求一条水平线和一条垂直线同时切，四块和相等，问题就复杂了。因为分割位置变成了一个二元组：(行切在哪里, 列切在哪里)。如果直接枚举这个二元组，就是 (m-1)(n-1) 个位置组合，每个组合再判断四块是否相等。这个复杂度看起来是 O(mn)，好像并不高，但如果我们能在判断之前就把大量不可能的候选位置筛掉，实际性能会好很多，尤其当矩阵特别大、元素特别稀疏时。
3.2 四块相等可以化简成三个等式
设整个矩阵的总和是 total，如果四个子矩阵和都相等，那每一块必然是 total/4，记为 target。所以第一步先判断 total 能否被 4 整除，如果不能，直接返回 false，省去后面所有计算。
接下来，设行分割线在第 r 行和第 r+1 行之间，列分割线在第 c 列和第 c+1 列之间。四个子矩阵分别是：
- 左上角：从 (0,0) 到 (r,c)，大小为 r+1 行 c+1 列
- 右上角：从 (0,c+1) 到 (r,n-1)
- 左下角：从 (r+1,0) 到 (m-1,c)
- 右下角：从 (r+1,c+1) 到 (m-1,n-1)
如果四个块都等于 target，肯定满足：
左上角 = target
右上角 = target，等价于“第一行的前 c+1 列 + 第一行的后 n-c-1 列”？不，我们换个更简洁的角度：上面两块的并集就是从 (0,0) 到 (r,n-1)，它的和是 pre[r][n]。如果左上角是 target，右上角也是 target，那么 pre[r][n] 必然等于 2target。反过来，如果 pre[r][n] = 2target 并且左上角等于 target，右上角自然就等于 target。
同理，左边两块的并集是从 (0,0) 到 (m-1,c)，它的和是 pre[m][c]。如果左上角是 target，左下角也是 target，那么 pre[m][c] 必然等于 2*target。
所以最终需要判断的就是三个条件：
- pre[r][n] == 2*target
- pre[m][c] == 2*target
- pre[r][c] == target
只要这三个条件都满足，右下角不用算也知道等于 target，因为 total - target - target - target = target。这个化简是整道题最核心的一步，它把“四个子矩阵的和都相等”变成了“三个前缀和位置上的值恰好匹配”，极大简化了枚举。
3.3 用哈希表管理候选行与候选列
既然条件这么清晰，哈希表就派上用场了。
先遍历所有可能作为行分割线的位置 r（取值范围是 1 到 m-1），如果 pre[r][n] == 2*target，说明在当前行切下去，上方两块的和大体上是够的，把这个 r 放进一个集合 rows。rows 里的每个元素都是可能满足整体条件的分割行。
再遍历所有可能作为列分割线的位置 c（取值范围是 1 到 n-1），如果 pre[m][c] == 2*target，说明在当前列切过去，左边两块的和大体上是够的，把这个 c 放进一个集合 cols。
最后只需要双重遍历 rows 和 cols，检查是否存在一个组合使得 pre[r][c] == target，存在就返回 true。
哈希集合在这里的作用是对候选位置做快速管理和去重。虽然行号和列号本身不会重复，但用 unordered_set 的语义更清晰：rows 里存的不是“所有行”，而是“有资格当分割线的行”，后续检查时只关心这些候选。在数据量大的情况下，候选集合通常远小于 m-1 和 n-1，双重遍历的实际代价会远低于 O(m*n)。
4. 核心实现：完整的 C++ 解答代码
4.1 代码先摆出来，再逐段拆
直接上代码，C++17 环境下可以直接跑：
class Solution { public: bool isPossibleToSplit(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<long long>> pre(m + 1, vector<long long>(n + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1]; } } long long total = pre[m][n]; if (total % 4 != 0) return false; long long target = total / 4; unordered_set<int> rows; for (int i = 1; i < m; ++i) { if (pre[i][n] == 2 * target) { rows.insert(i); } } unordered_set<int> cols; for (int j = 1; j < n; ++j) { if (pre[m][j] == 2 * target) { cols.insert(j); } } if (rows.empty() || cols.empty()) return false; for (int r : rows) { for (int c : cols) { if (pre[r][c] == target) { return true; } } } return false; } };代码结构其实很清晰，总共四步：构建二维前缀和、判断总和是否能被 4 整除、收集候选行和候选列、检查候选组合中是否存在恰好让左上角等于 target 的位置。
这里有一个值得说明的点：为什么行和列的循环条件里 i 从 1 到 m-1、j 从 1 到 n-1？因为分割线必须把矩阵切成非空块，所以行分割线不能在第 0 行之前，也不能在第 m 行之后。用 pre[i][n] 表示的是前 i 行整行的和，i 的取值范围自然就是 1 到 m-1。同理，列也是 1 到 n-1。如果矩阵是 1 行或者 1 列，那根本不可能切出四个非空子矩阵，直接返回 false 就行。上面代码里 rows 和 cols 至少有一个会是空集，所以最终会返回 false，逻辑是自动覆盖住这个边界的。
4.2 几个容易被忽视的边界与特殊情况
先聊 total % 4 != 0 这个判断。有些同学会漏掉这一步，直接用 total / 4 得到 target，然后继续计算。当 total 不能被 4 整除时，整数除法会向下取整，最后可能碰巧找到一个组合满足这三个条件，但实际上四个块的和并不完全相等。举个小例子，total = 14，target 算出来是 3，如果某个组合的 pre[r][c] 恰好等于 3，pre[r][n] 恰好等于 6，pre[m][c] 恰好等于 6，你会误判为 true，但真实情况下你根本不可能把总和为 14 的矩阵切成四块和都为 3.5 的整数和。所以整除判断不是优化，是正确性必需。
还有一个容易忽略的细节是矩阵元素是否非负。题目如果没有特殊说明，元素有可能是负数。如果元素为负，前缀和数组不满足单调性，但这题的核心判断条件依然成立，因为四块和相等本质上是一个等式条件，和元素正负无关。我们的三个简化条件是基于代数推导出来的，负数也不影响。所以代码不需要针对负数做额外处理。
如果矩阵的行或列特别小，比如 m = 2, n = 2，能不能切？可以，行分割线只有一条，列分割线也只有一条，四个块都是单元素。这种情况代码也能处理。但如果 m = 1 或者 n = 1，就没有合法的行列分割线，rows 或 cols 会是空集，自然返回 false。
4.3 复杂度和内存占用
时间复杂度分两部分看：构建前缀和是 O(mn)，收集候选行和候选列分别是 O(m) 和 O(n)，最后双重检查最多 O((m-1)(n-1))，也就是 O(mn)。整体最坏情况是 O(mn)，空间复杂度也是 O(m*n)，因为存了一个同样大小的前缀和数组。
哈希集合本身的空间是 O(m+n)，相对前缀和来说可以忽略不计。很多同学可能会问，既然最坏复杂度还是 O(m*n)，那哈希表的意义在哪？我的观点是，它让“哪些位置真正有可能成为分割线”这个信息变得可查询，而不需要每次都对所有行和所有列做一次完整扫描。在真实数据里，符合条件的候选行和候选列数量通常会远小于 m 和 n，所以实际运行时间会明显优于纯双重枚举。更重要的是，这个思路是很多矩阵分割题目的通用范式，把“需要同时满足多个坐标条件”的问题拆成“先分别收集单维候选，再检查交叉组合”。
5. 常见问题与排查实录
5.1 为什么我的结果总是差一点：类型溢出
我刷题群里几乎每周都有人问类似问题：“我的逻辑明明是对的，为什么跑大数据就错？”点进去十有八九是 int 溢出。LeetCode 不告诉你 m 和 n 的上限，矩阵元素范围也可能给到 1e9，这时候 pre 数组里随便一个值都可能超过 2^31 - 1，用 int 存就是未定义行为。
排查方式很简单：把 pre 和相关变量全改成 long long，再看提交结果。如果改了之后 AC，那基本就是溢出的问题。如果你怀疑某个数据范围，可以自己造一个 1000x1000 全是 1e9 的矩阵，跑一遍看看是否报错。老实说，我现在写这类题，只要看到“矩阵元素和”四个字，就已经条件反射用 long long 了，这能帮你省下不少调试时间。
5.2 为什么输出 false 但手动算是对的：条件漏了
最常见的错误版本是只判断了 pre[r][c] == target，也就是只看左上角那块是不是 target，然后直接返回 true。这样会漏掉一个关键条件：右上角、左下角也必须等于 target。
举个例子，假设 total = 16，target = 4，存在一个位置 r 使得 pre[r][c] = 4，但 pre[r][n] = 6，而不是 8。那么在 r 行上方，两块的分布是左上 4、右上 2，明显右边那块不满足。只看左上角就会误判成 true。
正确的做法就是我前面讲的三个条件：pre[r][n] == 2target、pre[m][c] == 2target、pre[r][c] == target。这三个条件缺一不可。我刷的时候也犯过这个错误，后来想明白了，多出来的两个条件本质上是把“右边那块和左下那块也必须等于 target”翻译成了前缀和数组上两个位置的相等判断。
5.3 哈希表真的是这题最优解吗：聊聊集合的作用
很多人看到题目标签里有哈希表，就会下意识觉得哈希表是用来把复杂度降到 O(m+n) 的。实际上这题的哈希表更多是扮演“候选集合”的角色，它的作用是快速定位候选行和候选列，减少不必要的交叉比较，而不是从算法层面把 O(m*n) 降成 O(m+n)。
如果你非要把这题写出一个严格 O(m+n) 的版本，也不是不可以，但要做更多假设，比如矩阵元素非负、前缀和单调递增，然后用双指针去同时推进行和列。但通常情况下，LeetCode 的标准解法就是前缀和加集合记录候选位置。所以刷这题的时候不用纠结“哈希表是不是最优解”，把它理解成一个管理候选位置的工具就好。你甚至可以用 vector 代替 unordered_set，逻辑也成立，只是集合语义上更贴近“去重后判断存在性”这个场景。
5.4 力扣每日一题刷题建议
说回“每日一题”这件事。很多人刷到中等题时总想一口吃成胖子，看完题面就希望立刻想出最优解，想不出来就焦虑。我的做法是分三步走：第一步，先用最暴力的方法把题目过了，不管复杂度，只要结果对就行，这样能确保你对题意没有理解偏差；第二步，分析哪里可以优化，通常是“要不要预处理”或“能不能减少枚举维数”；第三步，把优化后的解法提交，然后去看看讨论区有没有更妙的做法。
这道 3548 就是特别适合练这三步的题目。暴力法能帮你把题意吃透，前缀和优化让你明白空间换时间的威力，而哈希集合的使用则是一个简化实现的好例子。这套思路放到任何矩阵类题目上都通用，尤其是那些看着就要反复求区域和的题。
最后再分享一个刷题小技巧：遇到这种需要“先收集候选再检查组合”的题，我会在草稿纸上先把需要满足的等式列出来，再想用什么数据结构去装候选。不要一开始就埋头写代码，让人工判断的ABC，变成代码里清晰的 if 条件，一次 AC 概率会大很多。
