题目描述
思路解析动画文字版
把这两条判定式刻进脑子:主对角线 i 等于 j,副对角线 i 加 j 等于 n 减 1。两条都加,奇数边长时正中心多算了一次要减回来。下面每一帧都在套这两条式子,先从 3 行 3 列、从主对角线开始走。
3x3 · 主对角线 i 等于 j：这是 3 行 3 列的矩阵。先走主对角线,也就是行号等于列号的那条:位置 (0,0)、(1,1)、(2,2),从左上到右下。右边面板记累加过程,现在和是 0。
主对角线 · 看 (0,0)：看主对角线上的格子 (0,0),行号 0 和列号 0 相等,确实在主对角线上,它的值是 1。
主对角线 · (0,0) 计入,和 1：把 1 加进对角线和,这一格变蓝表示已经计入,和现在是 1。主对角线还没走完,接着看下一格。
主对角线 · 看 (1,1)：看主对角线上的格子 (1,1),行号 1 和列号 1 相等,确实在主对角线上,它的值是 5。
主对角线 · (1,1) 计入,和 6：把 5 加进对角线和,这一格变蓝表示已经计入,和现在是 6。主对角线还没走完,接着看下一格。
主对角线 · 看 (2,2)：看主对角线上的格子 (2,2),行号 2 和列号 2 相等,确实在主对角线上,它的值是 9。
主对角线 · (2,2) 计入,和 15：把 9 加进对角线和,这一格变蓝表示已经计入,和现在是 15。主对角线三格全加完了。
主对角线走完 · 和 15：主对角线 1、5、9 都加完了,和是 15。接下来走副对角线,也就是行号加列号等于 n 减 1 的那条;这里 n 是 3,所以是 i 加 j 等于 2,位置 (0,2)、(1,1)、(2,0),从右上到左下。
副对角线 · 看 (0,2)：看副对角线上的格子 (0,2),行号 0 加列号 2 等于 2,正好是 n 减 1,在副对角线上,值是 3。
副对角线 · (0,2) 计入,和 18：它不是正中心,放心加。把 3 加进和,这一格变蓝,和现在是 18。
副对角线 · 看 (1,1)：看副对角线上的格子 (1,1),行号 1 加列号 1 等于 2,正好是 n 减 1,在副对角线上,值是 5。不过要小心,这一格行号也等于列号。
正中心 (1,1) · 已算过,跳过：这一格 (1,1) 行号等于列号、又满足 i 加 j 等于 2,正是矩阵的正中心,它在主对角线那趟已经把 5 算过一次了。n 是 3 这种奇数,两条对角线在正中心交叉,为了不重复,这一趟把它标红跳过,不再加,和还是 18。
副对角线 · 看 (2,0)：看副对角线上的格子 (2,0),行号 2 加列号 0 等于 2,正好是 n 减 1,在副对角线上,值是 7。
副对角线 · (2,0) 计入,和 25：它不是正中心,放心加。把 7 加进和,这一格变蓝,和现在是 25。
3x3 答案 · 25：两条对角线都走完了。主对角线 1、5、9,副对角线又加了 3 和 7,正中心的 5 只算了一次。一共五个格子,1 加 5 加 9 加 3 加 7 等于 25,这就是答案。注意如果不去重,把中心 5 多加一次,就会错成 30。
4x4 · 偶数边长对照：再看一个 4 行 4 列的矩阵,n 是 4,是偶数。还是加两条对角线,留意一下它和刚才 3 乘 3 有什么不一样。先走主对角线,i 等于 j,位置 (0,0)、(1,1)、(2,2)、(3,3)。
主对角线 · (0,0) 计入,和 1：主对角线格子 (0,0) 值是 1,行号等于列号,加进和,和到 1。
主对角线 · (1,1) 计入,和 7：主对角线格子 (1,1) 值是 6,行号等于列号,加进和,和到 7。
主对角线 · (2,2) 计入,和 18：主对角线格子 (2,2) 值是 11,行号等于列号,加进和,和到 18。
主对角线 · (3,3) 计入,和 34：主对角线格子 (3,3) 值是 16,行号等于列号,加进和,和到 34。主对角线四格加完,和 34。
副对角线 · (0,3) 计入,和 38：副对角线格子 (0,3) 值是 4,行号 0 加列号 3 等于 3,在副对角线上,加进和,和到 38。
副对角线 · (1,2) 计入,和 45：副对角线格子 (1,2) 值是 7,行号 1 加列号 2 等于 3,在副对角线上,加进和,和到 45。
副对角线 · (2,1) 计入,和 55：副对角线格子 (2,1) 值是 10,行号 2 加列号 1 等于 3,在副对角线上,加进和,和到 55。
副对角线 · (3,0) 计入,和 68：副对角线格子 (3,0) 值是 13,行号 3 加列号 0 等于 3,在副对角线上,加进和,和到 68。副对角线四格也加完了。
4x4 · 没有公共正中心：关键的不一样在这里:n 等于 4 是偶数,正中心落在四个格子正中间,不是某一个具体格子,所以两条对角线一个公共格子都没有,八个格子互不重叠,各加一次就好,不用减谁。这正是奇数和偶数边长的区别。
4x4 答案 · 68：八个格子全加完,主对角线 1、6、11、16 是 34,副对角线 4、7、10、13 也是 34,没有重叠不用减,合计 68。对比 3 乘 3 那次要减中心,这次干干净净,这就是边长奇偶带来的差别。
边界想清:单格自己就是正中心只算一次、偶数边长无重叠直接相加、奇数边长去掉重复的正中心。
面试重点:副对角线判定是 i 加 j 等于 n 减 1、只有奇数边长才有公共正中心需要去重、一个循环按行走即可同时加两条线并去重。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def diagonalSum(self, mat: List[List[int]]) -> int: ans = 0 n = len(mat) for i, row in enumerate(mat): j = n - i - 1 ans += row[i] + (0 if j == i else row[j]) return ans复杂度
- 时间：O(n)，n 是矩阵边长。两条对角线最多 2n 个格子,n 为奇数时正中心重合、不同格子数是 2n 减 1,不管哪种都跟 n 成正比,按行走一遍每行最多看两个元素,根本不用扫整个 n 乘 n 的矩阵
- 空间：O(1)，从头到尾只用一个累加变量记答案,再加几个下标变量,不随矩阵规模增长,峰值占用是常数
易错点
面试追问把动画讲成自己的话
追问怎么快速判断一个格子在不在副对角线上?
追问为什么只有 n 是奇数时才需要去重?
追问能不能不分两趟、用一个循环就求完?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出星型图的中心节点
LeetCode 1791 · 简单 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题