矩阵对角线元素的和 图解题解
这道题到底在问什么
- 输入
- mat=[[1,2,3],[4,5,6],[7,8,9]]
- 输出
- 25
- 输入
- mat=[[5]]
- 输出
- 5
最优解：一步一步想明白
- 3把这两条判定式刻进脑子:主对角线 i 等于 j,副对角线 i 加 j 等于 n 减 1。两条都加,奇数边长时正中心多算了一次要减回来。下面每一帧都在套这两条式子,先从 3 行 3 列、从主对角线开始走。
- 4橙 = 正在看的格,蓝 = 已计入对角线和这是 3 行 3 列的矩阵。先走主对角线,也就是行号等于列号的那条:位置 (0,0)、(1,1)、(2,2),从左上到右下。右边面板记累加过程,现在和是 0。
- 5行号 0 等于 列号 0,在主对角线上看主对角线上的格子 (0,0),行号 0 和列号 0 相等,确实在主对角线上,它的值是 1。
- 6主对角线和累计 1把 1 加进对角线和,这一格变蓝表示已经计入,和现在是 1。主对角线还没走完,接着看下一格。
- 7行号 1 等于 列号 1,在主对角线上看主对角线上的格子 (1,1),行号 1 和列号 1 相等,确实在主对角线上,它的值是 5。
- 8主对角线和累计 6把 5 加进对角线和,这一格变蓝表示已经计入,和现在是 6。主对角线还没走完,接着看下一格。
- 9行号 2 等于 列号 2,在主对角线上看主对角线上的格子 (2,2),行号 2 和列号 2 相等,确实在主对角线上,它的值是 9。
- 10主对角线和累计 15把 9 加进对角线和,这一格变蓝表示已经计入,和现在是 15。主对角线三格全加完了。
- 111 加 5 加 9 等于 15主对角线 1、5、9 都加完了,和是 15。接下来走副对角线,也就是行号加列号等于 n 减 1 的那条;这里 n 是 3,所以是 i 加 j 等于 2,位置 (0,2)、(1,1)、(2,0),从右上到左下。
- 12行号 0 加 列号 2 等于 2看副对角线上的格子 (0,2),行号 0 加列号 2 等于 2,正好是 n 减 1,在副对角线上,值是 3。
- 13副对角线累加中 · 和 18它不是正中心,放心加。把 3 加进和,这一格变蓝,和现在是 18。
- 14行号 1 加 列号 1 等于 2看副对角线上的格子 (1,1),行号 1 加列号 1 等于 2,正好是 n 减 1,在副对角线上,值是 5。不过要小心,这一格行号也等于列号。
- 15n 是奇数,正中心只算一次这一格 (1,1) 行号等于列号、又满足 i 加 j 等于 2,正是矩阵的正中心,它在主对角线那趟已经把 5 算过一次了。n 是 3 这种奇数,两条对角线在正中心交叉,为了不重复,这一趟把它标红跳过,不再加,和还是 18。
- 16行号 2 加 列号 0 等于 2看副对角线上的格子 (2,0),行号 2 加列号 0 等于 2,正好是 n 减 1,在副对角线上,值是 7。
- 17副对角线累加中 · 和 25它不是正中心,放心加。把 7 加进和,这一格变蓝,和现在是 25。
- 18主 15 + 副 3 与 7,中心 5 只算一次 = 25两条对角线都走完了。主对角线 1、5、9,副对角线又加了 3 和 7,正中心的 5 只算了一次。一共五个格子,1 加 5 加 9 加 3 加 7 等于 25,这就是答案。注意如果不去重,把中心 5 多加一次,就会错成 30。
- 19看看 n 是偶数时有没有正中心再看一个 4 行 4 列的矩阵,n 是 4,是偶数。还是加两条对角线,留意一下它和刚才 3 乘 3 有什么不一样。先走主对角线,i 等于 j,位置 (0,0)、(1,1)、(2,2)、(3,3)。
- 20主对角线累加 · 和 1主对角线格子 (0,0) 值是 1,行号等于列号,加进和,和到 1。
- 21主对角线累加 · 和 7主对角线格子 (1,1) 值是 6,行号等于列号,加进和,和到 7。
- 22主对角线累加 · 和 18主对角线格子 (2,2) 值是 11,行号等于列号,加进和,和到 18。
- 23主对角线累加 · 和 34主对角线格子 (3,3) 值是 16,行号等于列号,加进和,和到 34。主对角线四格加完,和 34。
- 24副对角线累加 · 和 38副对角线格子 (0,3) 值是 4,行号 0 加列号 3 等于 3,在副对角线上,加进和,和到 38。
- 25副对角线累加 · 和 45副对角线格子 (1,2) 值是 7,行号 1 加列号 2 等于 3,在副对角线上,加进和,和到 45。
- 26副对角线累加 · 和 55副对角线格子 (2,1) 值是 10,行号 2 加列号 1 等于 3,在副对角线上,加进和,和到 55。
- 27副对角线累加 · 和 68副对角线格子 (3,0) 值是 13,行号 3 加列号 0 等于 3,在副对角线上,加进和,和到 68。副对角线四格也加完了。
- 28n 偶数,两条对角线不相交关键的不一样在这里:n 等于 4 是偶数,正中心落在四个格子正中间,不是某一个具体格子,所以两条对角线一个公共格子都没有,八个格子互不重叠,各加一次就好,不用减谁。这正是奇数和偶数边长的区别。
- 29主 34 + 副 34 = 68(无去重)八个格子全加完,主对角线 1、6、11、16 是 34,副对角线 4、7、10、13 也是 34,没有重叠不用减,合计 68。对比 3 乘 3 那次要减中心,这次干干净净,这就是边长奇偶带来的差别。
⚠️ 容易写错的地方
✗ 错：n 是奇数时把正中心加了两次
✓ 对：正中心同时在两条对角线上,只能算一次,要减掉一次或在副对角线那趟跳过它
本例 3 乘 3 的正中心 5 若不去重,答案会从 25 错成 30,这是这道题第一大坑
✗ 错：副对角线下标算错,写成 j 等于 n 减 i
✓ 对：副对角线是 i 加 j 等于 n 减 1,所以 j 等于 n 减 1 减 i
少减了 1 会整条对角线错位、甚至下标越界,务必记牢 n 减 1
✗ 错：n 是偶数时也去画蛇添足地减中心
✓ 对：偶数边长两条对角线没有公共格子,不存在重复,不能减
本例 4 乘 4 八个格子互不重叠,误减会让答案偏小
✗ 错：以为要把整个矩阵扫一遍才能求和
✓ 对：只走两条对角线就够,时间 O(n) 而不是 O(n 的平方)
对角线元素的位置由 i 和 j 的关系直接定位,不需要遍历每个格子
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int diagonalSum(vector<vector<int>>& mat) {
int ans = 0;
int n = mat.size();
for (int i = 0; i < n; ++i) {
int j = n - i - 1;
ans += mat[i][i] + (i == j ? 0 : mat[i][j]);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int diagonalSum(int[][] mat) {
int ans = 0;
int n = mat.length;
for (int i = 0; i < n; ++i) {
int j = n - i - 1;
ans += mat[i][i] + (i == j ? 0 : mat[i][j]);
}
return ans;
}
}复杂度
时间
O(n)
n 是矩阵边长。两条对角线最多 2n 个格子,n 为奇数时正中心重合、不同格子数是 2n 减 1,不管哪种都跟 n 成正比,按行走一遍每行最多看两个元素,根本不用扫整个 n 乘 n 的矩阵
空间
O(1)
从头到尾只用一个累加变量记答案,再加几个下标变量,不随矩阵规模增长,峰值占用是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 矩阵对角线元素的和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么快速判断一个格子在不在副对角线上?+
看它的行号加列号。如果行号 i 加列号 j 正好等于 n 减 1,它就在副对角线上。比如 3 乘 3 里,(0,2)、(1,1)、(2,0) 的行列号之和都是 2,也就是 n 减 1,所以它们都在副对角线上。主对角线则是行号等于列号 i 等于 j。
为什么只有 n 是奇数时才需要去重?+
正中心要同时满足 i 等于 j 和 i 加 j 等于 n 减 1。把第一个式子代进第二个,得到 2i 等于 n 减 1,也就是 i 等于 n 减 1 再除以 2。只有当 n 是奇数时,n 减 1 是偶数,i 才是一个合法的整数下标,这时两条对角线才有公共格子;n 是偶数时 i 算出来不是整数,两条线没有交点,自然不用去重。
能不能不分两趟、用一个循环就求完?+
可以,这也是参考代码的写法。按行从上往下走,对每一行 i,先加上主对角线元素 mat 第 i 行第 i 列,再令 j 等于 n 减 1 减 i,如果 j 不等于 i 就再加上 mat 第 i 行第 j 列;当 j 等于 i 时说明这一格是正中心、主对角线已经加过,就跳过。一趟循环既加了两条对角线,又顺手完成了去重。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 矩阵对角线元素的和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。