一、题目描述

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。

请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

示例??1：

输入：mat = [[1,2,3],
? ? ? ? ? ? ? ? ? ? ? [4,5,6],
? ? ? ? ? ? ? ? ? ? ? [7,8,9]]
输出：25
解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25
请注意，元素 mat[1][1] = 5 只会被计算一次。

示例??2：

输入：mat = [[1,1,1,1],
? ? ? ? ? ? ? ? ? ? ? [1,1,1,1],
? ? ? ? ? ? ? ? ? ? ? [1,1,1,1],
? ? ? ? ? ? ? ? ? ? ? [1,1,1,1]]
输出：8

示例 3：

输入：mat = [[5]]
输出：5

提示：

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

二、思路

元素总和等于主副对角线去掉重复元素之和，如果二维数组长度是奇数，则去掉最中间的元素。

假设i是二维数组的层号，第一层时，i=0；length为二维数组的长度，那么

? ? ? 主对角线上的元素，依次是(0,0)、（1,1）、（2,2）...(length-1,length-1)

? ? ? 副对角线上的元素，依次是(0,length-1)、（1,length-2）、（2,length-3）...(i,0)

该方案的时间复杂度为O(n)，空间复杂度为O(1)。

三、代码实现

    public int diagonalSum(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return 0;
        }

        int sum = 0;
        int length = mat.length;
        for (int i = 0; i < mat.length; i++) {
            //主对角线,例如(0,0)、（1,1）、（2,2）...(length-1,length-1)
            sum += mat[i][i];
            //副对角线,例如(0,length-1)、（1,length-2）、（2,length-3）...(i,0)
            sum += mat[i][length - i - 1];
        }

        //如果是奇数长度，则去掉重复计算的数，即数组中间的数
        if (length % 2 == 1) {
            sum -= mat[length / 2][length / 2];
        }

        return sum;
    }