这个题目放在每日一题里其实挺冷门的见过的人不多但做过的都知道它属于那种“一看就会一写就卡”的类型。你要是直接暴力枚举思路三分钟就能想完代码也能跑但最后提交的时候十有八九会挂在超时上。而解法二——前缀和优化——才是这道题真正想考察的东西怎么把二维矩阵里的重复求和计算用前缀和变成 O(1) 查询从而把整体复杂度压到一个能看的量级。我这次就直接围绕解法二来讲把前缀和怎么设计、为什么要这么设计、以及我在实现过程中踩过的坑一次性讲透。1. 题目理解与思路演进1.1 这个题目到底在问什么先讲人话。幻方这个概念说穿了就是一个方阵里每一行相加、每一列相加再加上两条对角线相加最后得到的数值全部相等。题目给的 grid 是一个 m x n 的整数矩阵你要从里面找出一个边长尽可能大的正方形子矩阵满足这个子矩阵恰好是一个幻方。注意关键词正方形、行和相等、列和相等、对角线相等缺一不可。行和相等指的是这个 k x k 子矩阵里第 1 行到第 k 行的每一行和都相等列和同理两条对角线是指主对角线和副对角线各自的和也要等于前面那个公共值。这里有个很容易忽略的点题目要求所有行、所有列、两条对角线总共 2k 2 个数值全部相等并不是说只有主对角线和副对角线的和相等就够了。1.2 从暴力到前缀和的演进逻辑如果你第一次接触这个题第一反应肯定是暴力枚举所有可能的左上角坐标 (i, j)枚举边长 k从 min(m, n) 往下递减然后对每个 k x k 子矩阵做一次双重循环求和验证。复杂度大约是 O(m * n * min(m, n) * k^2)在 m、n 都到 50 时勉强能跑但题目数据范围如果大到 10^3这个复杂度直接就炸了。解法一的思路通常是用哈希表或数学技巧减少一些重复计算但本质上还不是最优。解法二的核心是提前把行、列、对角线的区间和用前缀和预处理出来让任何一个子矩阵的行和、列和、对角线和都能在 O(1) 时间内取到于是验证过程就从 O(k^2) 降到了 O(k)整体复杂度变成 O(m * n * min(m, n))。这个思路理解起来不难但真正动手写的时候会发现对角线前缀和比行列前缀和要麻烦不少索引关系的处理是最大的坑。2. 前缀和数组的设计与细节2.1 行前缀和与列前缀和先看最简单的一维前缀和怎么拓到二维。因为我们要频繁求“第 i 行从第 c1 列到第 c2 列的和”那么很自然地对每一行分别做一次一维前缀和。设 rowPrefix[i][j 1] 表示第 i 行前 j1 个数的和那么第 i 行从第 c1 列到第 c2 列的和就是sum_row(i, c1, c2) rowPrefix[i][c2 1] - rowPrefix[i][c1]举个具体例子。假设矩阵第 0 行是 [1, 2, 3, 4]那么 rowPrefix[0] [0, 1, 3, 6, 10]。想求第 0 行第 1 列到第 3 列即 2 3 4的和用 rowPrefix[0][4] - rowPrefix[0][1] 10 - 1 9正确。列前缀和也是一样的道理colPrefix[i 1][j] 表示第 j 列前 i1 个数的和求第 r1 行到第 r2 行、第 j 列的和就是 colPrefix[r2 1][j] - colPrefix[r1][j]。这里为什么建议大家用 0 开头、1-based 的偏移写法因为这样省掉了“如果 c1 0 就特判”的麻烦。统一用 j 1 作为右端点用 j 作为左端点边界就自动兼容了。这是写前缀和的通用习惯不只是这个题很多二维区间求和题都建议这么写。2.2 两条对角线前缀和这里是最容易写错的地方主对角线前缀和相对好理解。如果从左上角 (r, c) 往右下角走每步 r1、c1。我们可以按照每一条主对角线分别维护前缀和但实际上更省心的做法是直接开一个二维数组 diagPrefix[i 1][j 1]让它表示从 (0, 0) 到 (i, j) 这条主对角线方向上的累加和即diagPrefix[i 1][j 1] diagPrefix[i][j] grid[i][j]那么从 (r, c) 开始向右下延伸 k-1 步的这条主对角线区间和就是sum_main_diag(r, c, k) diagPrefix[r k][c k] - diagPrefix[r][c]很多第一次写的人会想当然写成 diagPrefix[r k][c k] - diagPrefix[r][c]实际上是对的因为 diagPrefix[r][c] 恰好就是终点之前那些数在同一个对角线上的累计。这是一个很巧妙的细节对角线区间和是两个端点处的对角线前缀和之差而不是像行前缀和那样涉及横纵两个方向的差值。副对角线就更有意思了。从 (r, c) 往左下角走每步 r1、c-1。这里如果你也用相同的二维数组方式维护那么递推关系是antiDiagPrefix[i 1][j 1] antiDiagPrefix[i][j 2] grid[i][j]注意第二维度方向是反的。写的时候要非常小心越界尤其是 j 2 这个下标在 j j 时可能超出列数。更推荐的做法是额外开一个 antiDiagPrefix定义 antiDiagPrefix[i 1][j] 表示第 i 行、第 j 列从矩阵右上方向左下方的累加和。根据副对角线方向我们可以用偏移量来表示从 (r, c) 沿着副对角线方向走 t 步到达 (r t, c - t)。所以如果想求从 (r, c) 向左下走 k-1 步的副对角线区间和等价于sum_anti_diag(r, c, k) antiDiagPrefix[r k][c - k 1] 的累计设计...其实这些花哨的写法都容易让人迷糊。我个人建议直接用两个与矩阵同形状的辅助数组但明确表示“从某个位置出发向左下方向的累计和”这样代码反而更好读。后面我会给出完整代码来说明。2.3 为什么不直接用二维前缀和很多人会问既然有二维前缀和套路为什么这里不用它来求每个子矩阵的行和列和原因很直接二维前缀和可以 O(1) 求出任意子矩阵的总和但它无法直接求“第 i 行的第 c1 列到第 c2 列”这种横条的和。你当然可以用二维前缀和先算整个 k x k 区域的总和然后减去某些部分来得到某一行但那样每次验证的常数会变大而且代码写起来完全没有“行、列、对角线”这种语义化的结构。等你调试的时候你看着那一堆加减表达式很容易搞混。反过来行和列分别用一维前缀和语义非常清晰。每一行的和是多少列和是多少直接下标一减就出来至于两条对角线的和用对角线方向的前缀和数组维护同样是直观的。这也是解法二的核心思路同一套前缀和思想针对不同方向分别设计数组。3. 完整实现与复杂度分析3.1 核心枚举策略前缀和准备好之后真正的验证就只剩两个环节枚举边长、枚举位置。推荐从大到小枚举边长即 k 从 min(m, n) 开始递减一旦找到符合条件的直接输出 k 并结束。为什么要从大到小因为题目只要求最大值你想找的是最大边长如果从小到大枚举你得把后面所有更大的边长方阵都全验证完才能确认当前是不是最大值而从大到小枚举第一个找到的必然是最大边长可以直接返回。枚举位置时注意边界左上角 (r, c) 必须满足 r k m即矩阵边界够。注意是 k 不是 k - 1因为长度为 k 的边需要访问 r 到 r k - 1 行所以 r k - 1 m等价于 r k m。左边界同理c k n。验证某位置上边长为 k 的方阵是否为幻方时按顺序做四件事求出目标值 target就是主对角线的和 sum_main_diag(r, c, k)。逐行验证每一行和是否等于 target。逐列验证每一列和是否等于 target。算出副对角线和验证是否等于 target。一旦有任何一个不等直接失败进入下一个位置。3.2 代码逐段讲解下面我把核心代码完整贴出来并逐段说明。先讲辅助数组初始化class Solution { public: int largestMagicSquare(vectorvectorint grid) { int m grid.size(), n grid[0].size(); vectorvectorint rowPref(m, vectorint(n 1, 0)); vectorvectorint colPref(m 1, vectorint(n, 0)); vectorvectorint mainDiag(m 1, vectorint(n 1, 0)); vectorvectorint antiDiag(m 1, vectorint(n 1, 0)); // 行前缀和 for (int i 0; i m; i) { for (int j 0; j n; j) { rowPref[i][j 1] rowPref[i][j] grid[i][j]; } } // 列前缀和 for (int j 0; j n; j) { for (int i 0; i m; i) { colPref[i 1][j] colPref[i][j] grid[i][j]; } } // 主对角线前缀和 // mainDiag[i 1][j 1] 从(0,0)到(i,j)沿主对角线累计 for (int i 0; i m; i) { for (int j 0; j n; j) { mainDiag[i 1][j 1] mainDiag[i][j] grid[i][j]; } } // 副对角线前缀和 // antiDiag[i 1][j] 从(i,j)向左下走到边界的累计这里我用更稳妥的方式 // 直接定义为 antiDiag[r][c] 表示从 (r,c) 向左下方向延伸到边界的累计和 // 初始化先填最后一行和第一列然后逐行向上填 vectorvectorint anti(m 1, vectorint(n 1, 0)); for (int i m - 1; i 0; i--) { for (int j 0; j n; j) { anti[i][j] grid[i][j] (i 1 m j - 1 0 ? anti[i 1][j - 1] : 0); } }顺着这个 anti 数组定义副对角线的区间和怎么取从 (r, c) 出发向左下走 k-1 步终点是 (r k - 1, c - k 1)。这个区间的和等于 anti[r][c]当前点一直延伸到边界的和减去 anti[r k][c - k]终点再往下走一个位置之后的延伸和。即int sumAnti(int r, int c, int k) { return anti[r][c] - (r k n ? anti[r k][c - k] : 0); }这个写法下副对角线区间的计算变得很直观因为它和行前缀和的“右端点减左端点”逻辑一模一样只是方向变成了左下。验证函数就简单多了int target mainDiag[r k][c k] - mainDiag[r][c]; // 每一行 for (int t 0; t k; t) { int sum rowPref[r t][c k] - rowPref[r t][c]; if (sum ! target) return false; } // 每一列 for (int t 0; t k; t) { int sum colPref[r k][c t] - colPref[r][c t]; if (sum ! target) return false; } // 副对角线 int sum anti[r][c] - (r k - 1 1 m - 1 ? anti[r k][c - k] : 0); if (sum ! target) return false;注意主对角线的取法mainDiag[r k][c k] 减 mainDiag[r][c]因为 mainDiag[i][j] 表示从 (0,0) 到 (i-1, j-1) 的累计。这一点在你编码时下标要非常清晰写错了会出现差一行的情况报错还很隐蔽。3.3 复杂度推导前缀和的预处理部分行、列、两个对角线方向都是 O(m * n) 的复杂度一次双重循环系数很小。枚举部分假设 s min(m, n)你对每个边长 k 做一次判断。每个边长 k 需要枚举的左上角数量大约 (m - k 1) * (n - k 1)。总枚举量可以估计为总验证次数 sum_{k1}^{s} (m - k 1) * (n - k 1)当 k 取单位值 1 时枚举数量差不多是 m * n当 k 取 1 到 s 加总时三个量级放在一起大致是 O(m * n * s)。因为每个验证内部要做 k 次行验证加 k 次列验证即 2k 个 O(1) 查询所以整体复杂度为O(m * n * s m * n * s^2) 的上界其实是被行、列循环拉开了一点更严谨一点讲验证一个方阵内所有行和列需要 2k 次 O(1) 查询。所以枚举的总代价是T(n, m) sum_{k1}^{s} (m - k 1) * (n - k 1) * 2k当 s 相对 m、n 较小时这个代价大概是 O(m * n * s^2)如果 s 趋近于 m 和 n简化计算大概是 O(s^4)。但通常 LeetCode 的数据规模下 s 不大这种复杂度是可以通过的。有人可能会想那是不是还要再优化比如用单调性之类的做二分但这个题的官方解法预期就是这样前缀和加从大到小枚举完全够用。如果一开始枚举边长时使用从大到小顺序并且一旦找到就直接 return实际运行时间还会比最坏情况好不少尤其是数据里存在一个接近 min(m, n) 的幻方时很快就能返回。4. 实际测试与踩坑记录4.1 我最初写错的三处地方第一处是行、列前缀和的维度顺序。我一开始把列前缀和也定义成 n 个一维数组每个长度 m结果取的时候下标绕来绕去把 colPref[i][j] 写成了 colPref[j][i]导致验证第 j 列时数据错位。折腾很久才意识到与其玩各种花式下标不如规规矩矩用第一维是 r 1、第二维是 c 的写法。这样 colPref[r 1][c] 表示前 r1 行第 c 列的累计和看起来更整齐。第二处是主对角线和副对角线的方向搞混。主对角线是右下方向所以递推里面 i1、j1 同时增加副对角线是左下方向递推里行增加、列减少。我在初始化 anti 数组时把列的方向写反了导致求副对角线和的时候发现结果总是偏小。最后检查后发现是“j - 1”和“j 1”写反。第三处是边界处理。枚举左上角坐标时我一开始用了r k - 1 m这种写法本来也没错但后面在所有边界判断里混用了和导致方阵恰好贴边界时少枚举一种情况。后来统一用r k m这种不容易出错的形式代码反而更干净。4.2 几个值得手测的用例第一个是极端的 1x1 矩阵比如[[10]]。任何一个 1x1 的方阵都满足幻方定义因为只有一行一列和一条对角线而这三个数都是同一个数题目样例一般不会给你这种但你自测时必须覆盖。代码里应天然能处理 k 1 的情况如果验证函数里 for 循环写得有问题k 1 时因为没有任何中间行和列要判断容易漏掉对角线的判断要多留心。第二个测试是边长 2 的简单情况比如4 1 1 4这个 2x2 方阵里主对角线为 8副对角线为 2行和分别为 5不满足幻方。正确结果应返回 1。测试时如果代码对 k 1 判定失败返回错误值那问题大概率出在“是否逐列验证”这一步。再测一个满足条件的 2x2 方阵2 2 2 2主对角线 4副对角线 4行和 4列和 4。正确结果应返回 2。这里的核心是副对角线正确取到值容易通过这个用例暴露出 anti 数组初始化方向错误。第三个是刻意构造一个 3x3 幻方混在一个 4x4 矩阵里8 1 6 9 3 5 7 8 4 9 2 1 9 1 2 3左上角的 3x3 方阵就是一个标准幻方各行、列、对角线都是 15。正确的输出应该是 3。如果你发现输出结果是 2说明你在枚举边长时循环结束条件写错了比如 k 从 min(m, n) 开始递减但你误用了k 0加上提前 return导致 k 3 时验证失败。你可以单步调试看 k 3 时到底是哪一步失败。4.3 关于枚举顺序的一个经验前面我说从大到小枚举边长但这个题里有一个额外的好处如果最大边长对应的幻方根本不存在你会快速退出很多无效的大 k 验证。验证大的 k 时代价高但数量少验证小的 k 时代价低但数量多。在随机数据下整体耗时分布其实相当均匀。有人可能好奇为什么不用二分查找边长因为“合法边长”这个性质不满足单调性——如果边长为 k 的方阵存在不代表边长 k-1 的方阵一定存在虽然理论上是存在的因为任何幻方的子矩阵并不必然是幻方但 k-1 可能不存在反而是最大合法值可以通过枚举法直接得到。而且二分的 check 复杂度也并不比直接枚举小多少所以没必要。5. 避坑指南与扩展思考5.1 前缀和的本质空间换时间的权衡这道题是典型的“空间换时间”模板。你花 O(m * n) 的内存存了四个方向的辅助数组换来了后续每次查询 O(1) 的代价。对于 m、n 都不超过 10^2 到 10^3 的数据规模多开几个二维数组毫无压力但如果矩阵特别大比如 10^4 级别四个二维数组就是接近 10^8 的 int 内存折合 400MB可能超限。这个时候就要在查询时计算还是预处理之间做取舍。一种折中方案是只额外存行、列两个前缀和对角线和每次现算。对角线计算需要 O(k) 时间。整体复杂度就从 O(m * n * s) 升到 O(m * n * s^2)但内存减半。LeetCode 这题的数据范围下完全够用牺牲一点时间换代码简洁度也是可选项。5.2 我看到的一些错误题解我逛题解区时发现有人在验证行和列时直接复用了二维前缀和然后写出类似getSum(r1, c1, r2, c2)的函数再手动减其它部分求某一行。这种写法虽然也能过但极难读懂而且一旦你方阵边长变大实际上每次验证都会做很多次二维前缀和调用常数很大容易踩时间线的边缘。相比之下分开维护行、列、对角线前缀和代码的意图一眼就能看懂自查也容易每一个“区间和”都是一个数组取两个下标之差不会出现多位加减混在一起的表达式。5.3 从这道题延伸出的更强思路如果你把“幻方”的概念抽象一下这题的本质就是“验证正方形区域内的行、列、对角线方向上的 k 个区间和全部相等”。只要区间和能 O(1) 查询验证就是 O(k)。你可以试着把它变形如果题目改成求最大矩形幻方宽高不等行和列分别相等但两条对角线只适用于正方形那处理方式就不太一样了。或者把“相加相等”改成“乘积相等”前缀和又得变成前缀积还要注意溢出的问题。这种举一反三的思维在刷题时挺值得培养。另外如果你将来在图像处理或者滑动窗口累加求和中用到类似结构这个“按方向分别做前缀和”的思路也可以迁移。比如在处理灰度图像的某种特征统计时你可能会需要快速获取任意斜线方向的像素累加和那么主对角线前缀和、副对角线前缀和就是现成的工具。5.4 初始化辅助数组时的一个习惯建议我强烈建议你在实现主对角线前缀和时直接把数组开成 m 1 行 n 1 列所有索引都从 1 开始映射。这样在第 0 行和第 0 列预留了天然的全 0 外边框递推的时候完全不用单独处理边界。比如 mainDiag[i 1][j 1] 取值时mainDiag[i][j] 一定存在并且第 0 行全 0天然满足边界定义。副对角线的前缀和则有点特殊因为它不是沿右下方向而是沿左下方向。如果你也把数组扩大成 m 1 行 n 1 列你可能会想要给右侧加一个全 0 列但这反而会让代码更难懂。我自己是用按行从下往上、按列从左往右的方式初始化 anti让 anti[r][c] 表示从 (r, c) 向左下延伸的和然后配合r k m c - k 0这类判断取区间和。整体来看条理也比较清楚。6. 一些小经验总结这是我个人的一点体会不代表最优解但确实让我在做这类前缀和题目时少走了很多弯路。第一写前缀和类题目时不要一上来就写代码先在纸上把“要查询哪些区间”列出来再有针对性地设计数组维度。比如这道题需要查四种区间行的横条、列的竖条、右下斜条、左下斜条。每种区间对应一个方向的前缀和列清楚后写代码时下标基本不会错。第二如果题目要求验证的区间种类很多不要吝啬内存。即使多开一两个辅助数组代码的稳定性和可读性也远超你硬凑一个数组去计算所有情况的收益。刷题时追求的是“一次 AC 并且代码好维护”而不是省那几 MB 内存。第三尽量把“判断一个方阵是否为幻方”抽成一个独立函数测试起来会方便很多。你可以直接把各类输入灌进去跑观察到底哪一步返回 false。我在实际调试中就曾用这个方法快速定位了副对角线方向写反的问题。第四LeetCode 这类题目的运行时间其实很不稳定不同语言常数差异也大。如果你发现从大到小枚举加上常规剪枝仍然偶尔超时试着把行和列的验证合并到一个循环里一个层循环同时对比 rowSum 和 colSum。这样能减少循环开销代码也更紧凑。但要注意不是把 rowSum 和 colSum 混在一个变量里仍然要分开求。最后说一个小技巧。如果你在枚举边长时发现某个位置已经不可能存在更大的幻方可以提前对剩余区间做面积判断。比如当(i maxK) m || (j maxK) n时就不用再尝试了。虽然效果不明显但配合从大到小的枚举顺序在某些极端数据上会省下最后几轮无谓的验证。这道题整体不算难难的是把四个前缀和方向理清楚以及把边界判断写对。如果你做完后能不看题解再独立写一遍并且把对角线前缀和的索引关系说明白那这一类“区间和相等判断”的题目基本都拿得下来。