题目描述
思路解析
一句话答案：LeetCode 1572 矩阵对角线元素的和：主对角线上行号等于列号、副对角线上行号加列号等于 n 减 1，两条逐行各取一格相加，n 为奇数时正中心被两条线共用只算一次，时间 O(n)、空间 O(1)。
对角线求和，到底要加哪些格子
给一个 n 行 n 列的正方形矩阵 mat，把它两条对角线上的元素加起来。主对角线是从左上角到右下角那条，副对角线是从右上角到左下角那条。题面例子是第一行 1、2、3，第二行 4、5、6，第三行 7、8、9 的方阵，答案 25；再小到 mat 只有一个数 5，答案就是 5。要留神两条对角线在正方形中间可能落到同一个格子上，题目要的是这个格子只算一次的和。
两条判定式，直接点到对角线上的格子
对角线上满打满算才 2n 个元素，把整张 n 乘 n 的表挨个格子扫一遍再挑，其余全是陪跑。好在对角线元素的位置有现成判定式：给一个格子记行号 i 和列号 j，它在主对角线上，当且仅当 i 等于 j；在副对角线上，当且仅当 i 加 j 等于 n 减 1。按行走，第 i 行里主对角线那格落在第 i 列，副对角线那格落在第 n 减 1 减 i 列，一步定位。唯一要当心两格会不会重合：当第 n 减 1 减 i 列正好等于第 i 列时，两条对角线在这行撞到一起，那格正是正方形的正中心，只有 n 是奇数才会发生，它在主对角线那趟已经加过，副对角线这趟就得跳过。
一趟循环，顺手把去重也做了
参考代码把它压成一趟循环。累加变量 ans 从零起，按行遍历：对第 i 行，先加上主对角线元素、即第 i 列的值；再令 j 等于 n 减 1 减 i，若 j 不等于 i，就把第 j 列的副对角线元素也加上；若 j 等于 i，说明撞上正中心、已经加过，直接跳过。走完 n 行，ans 就是答案，求和与去重一次遍历全办了。
拿题面这个 3 乘 3 矩阵手算一遍
还是第一行 1、2、3、第二行 4、5、6、第三行 7、8、9 这个矩阵，n 是 3。先走主对角线：第 0 行取 1，第 1 行取 5，第 2 行取 9，和是 1 加 5 加 9 等于 15。再走副对角线，n 减 1 是 2：第 0 行取第 2 列的 3；第 1 行副对角线列 n 减 1 减 1 还是第 1 列，和主对角线撞在一起、落在正中心 5，跳过不加；第 2 行取第 0 列的 7。
合起来 15 加 3 加 7 等于 25，正中心的 5 只算一次，和题面答案对得上。要是忘了去重、把中心的 5 再加一遍，就会从 25 错成 30，这是本题最常见的失分点。
偶数边长别多减，单格矩阵就是它自己
先说奇偶这道坎。n 是奇数时两条对角线在正中心交叉，那格必须去重；可 n 是偶数时，正中心落在四个格子正当中、不落到任何具体格子，两条线一个公共格都没有，八格各加一次，这时再减中心反而把答案算小了。副对角线下标是 j 等于 n 减 1 减 i，少减那个 1、写成 j 等于 n 减 i，整条对角线都会错位甚至越界。最小的边界是单格矩阵，n 是 1，那个数既在主对角线又在副对角线正中心上，只算一次，答案就是它本身，也就是题面第二个例子里那个 5。
复杂度上，全程按行走一遍、每行最多看两个格子，最多 2n 个、跟边长成正比，时间 O(n)，不必扫整张 n 乘 n 的表；空间上只用一个累加变量，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
把这两条判定式刻进脑子:主对角线 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题