前言

這篇是我在解 HackerRank Diagonal Difference 時的刷題筆記。

題目本身是經典矩陣題, 但它的重點其實不只是加總, 而是能不能快速看出兩條對角線的座標規律。更有意思的是, 同一題在 TypeScript 與 Java 會碰到不同的語法手感: arr[i][j] 和 arr.get(i).get(j) 背後是完全不同的資料結構思維。

題目要求與座標規律推導

題目給定一個 $N \times N$ 的方陣（Square Matrix）, 要求計算「主對角線（左上到右下）」與「副對角線（右上到左下）」元素總和的絕對差值。

面對這種矩陣座標題, 我習慣先把索引關係畫出來, 直接找規律:

假設為 6x6 矩陣:
列 (i) = 0: [0][5] (右)  [0][0] (左) -> R: 5, L: 0
列 (i) = 1: [1][4] (右)  [1][1] (左) -> R: 4, L: 1
列 (i) = 2: [2][3] (右)  [2][2] (左) -> R: 3, L: 2
列 (i) = 3: [3][2] (右)  [3][3] (左) -> R: 2, L: 3
...
列 (i) = 5: [5][0] (右)  [5][5] (左) -> R: 0, L: 5

整理後的核心規律如下:

  • 主對角線（Left-to-right）: 列索引與行索引永遠相等, 也就是 arr[i][i].
  • 副對角線（Right-to-left）: 列索引與行索引相加永遠等於 length - 1, 也就是 arr[i][length - 1 - i].

找到這個規律後, 就能從兩層巢狀迴圈的 $O(N^2)$, 優化成單層迴圈的 $O(N)$, 一次收割兩條對角線。

TypeScript 寫法: 屬性與解構

function diagonalDifference(arr: number[][]): number {
  let right: number = 0;
  let left: number = 0;
  const { length } = arr;

  for (let i: number = 0; i < length; i++) {
    right += arr[i][length - 1 - i];
    left += arr[i][i];
  }

  return Math.abs(left - right);
}

TypeScript 核心觀念

  1. length 是屬性, 不是方法: 在 JS/TS 中是 arr.length, 不需要括號.
  2. 可以解構出 length: const { length } = arr 讓程式更精簡, 也能降低手誤拼字風險.
  3. 陣列存取是中括號語法: 二維陣列直接 arr[i][j].

Java 寫法: List 介面與拆箱

HackerRank 在 Java 通常給的是 List<List<Integer>>, 而不是 int[][]。因此長度與索引存取都要改用集合框架語法。

class Result {
    public static int diagonalDifference(List<List<Integer>> arr) {
        int right = 0;
        int left = 0;
        int length = arr.size();

        for (int i = 0; i < length; i++) {
            right += arr.get(i).get(length - 1 - i);
            left += arr.get(i).get(i);
        }

        return Math.abs(right - left);
    }
}

Java 核心機制

  1. size() 是方法: List 取得長度必須呼叫 arr.size().
  2. 連環 get: List<List<T>> 不能寫 arr[i][j], 要寫 arr.get(i).get(j).
  3. Auto-unboxing: Integer 在 += 與 int 運算時, 編譯器會自動拆箱成原生型別。

跨語言語法對照

環境與型別獲取長度 (Length / Size)元素取值 (Access)類別本質
JS / TS 陣列 (number[][])arr.lengtharr[i][j]特殊物件
Java 原生陣列 (int[][])arr.lengtharr[i][j]原生陣列物件
Java 集合框架 (List<List<T>>)arr.size()arr.get(i).get(j)集合物件
Java 字串 (String)str.length()str.charAt(i)類別物件

複雜度分析

  • 時間複雜度（Time Complexity）: $O(N)$, 只需一層迴圈掃過每一列一次.
  • 空間複雜度（Space Complexity）: $O(1)$, 只使用固定數量的輔助變數.

核心體悟

  1. 計算前先找規律: 矩陣題先畫索引座標, 常常比直接寫雙迴圈更快收斂.
  2. 跨語言要先校準容器模型: JS/TS 陣列、Java 原生陣列、Java List 在「長度與索引」上是三套語法.
  3. 一題雙解很值得: 同時訓練演算法直覺與語言肌肉記憶, 對面試與實戰都很有幫助.

總結

這題的核心不是算加減, 而是看你能不能用座標規律把問題降維。

  • 規律抓到後, 雙對角線可在單層迴圈中同時計算.
  • TypeScript 的 arr.length 與解構語法讓程式更精簡.
  • Java 的 List<List<Integer>> 則提醒我們回到集合介面的基本功.

參考資料