1572. 矩阵对角线元素的和

题目链接

给定一个正方形矩阵，返回对角线元素的和（两条对角线，中心的元素不要叠加两次）。

第一种方法：遍历矩阵

矩阵中某个位置（i, j）如果处于对角线上。则一定满足下列条件之一：

• i = j;
• i + j = n - 1;

根据上边的结论，可以遍历整个矩阵。如果满足条件之一，则表示该元素在对角线上，加入到答案中。根据矩阵的行数为奇数还是偶数，来决定是否减去中心元素。

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        return sum(mat[i][j] for i in range(n) for j in range(n) \
                    if i == j or i + j == n - 1)

复杂度分析：

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

第二种方法：枚举对角线元素

逐行遍历，记录当前行号为i，则当前行中处于对角线的元素为：坐标（i，i）和坐标（i，n-i-1），因此把（i，i）和（i，n-i-1）处的数字加入到答案中。如果n是奇数的话，则主对角线与副对角线存在交点（[n/2], [n/2]），该点会被计算两次。所以当n为奇数的时候，需要减掉交点处的值。

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        total = 0
        mid = n // 2
        for i in range(n):
            total += mat[i][i] + mat[i][n - 1 - i]
        return total - mat[mid][mid] * (n & 1)

复杂度分析：

时间复杂度：O(n)，其中n是矩阵mat的行数

空间复杂度：O(1)

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        n = len(mat)
        i = 0
        j = n - 1
        sum = 0
        while i < n:
            # 如果是正中心的元素
            if i == j:
                sum += mat[i][j]
            else:
                # 左上和右上开始遍历
                sum += mat[i][i] + mat[i][j]
            i += 1
            j -= 1

        return sum