解題說明
Matrix Diagonal Sum
題目描述：
給定一個 n × n 的正方形矩陣 mat，計算其主對角線和副對角線上所有元素的總和。如果某個元素同時在兩條對角線上（即矩陣中心元素，僅當 n 為奇數時），只計算一次。
解題思路： 遍歷矩陣的每一行 i：
- 主對角線元素為
mat[i][i] - 副對角線元素為
mat[i][n-1-i]
將兩者都加入總和。當 n 為奇數時，中心位置 i == n-1-i，此時同一元素被加了兩次，需要在最後減去一次。
C++ 解法
複雜度分析
時間複雜度：O(n) — 只需遍歷一次矩陣的 n 行，每行做常數操作。
空間複雜度：O(1) — 只使用常數額外空間。
虛擬碼
1. Let n = number of rows in mat 2. Initialize sum = 0 3. For each row i from 0 to n-1: a. sum += mat[i][i] (primary diagonal) b. sum += mat[i][n-1-i] (secondary diagonal) 4. If n is odd: a. sum -= mat[n/2][n/2] (remove double-counted center) 5. Return sum
其他解法
條件判斷法 O(n)：在迴圈中檢查 i != n-1-i 再決定是否加副對角線元素，避免事後減去中心。邏輯稍微複雜但省去最後的判斷。
雙重迴圈遍歷 O(n²)：遍歷整個矩陣，對每個元素檢查是否在對角線上。時間複雜度較差，不建議使用。
延伸思考
- 如果矩陣不是正方形（m × n），如何定義並計算對角線之和？
- 如果需要計算所有平行於主對角線的對角線之和，該如何實現？
- 能否用矩陣的 trace（跡）性質直接求主對角線之和？