主題: 學習筆記

LeetCode 2574：TypeScript 左右總和差

比較建立左右總和陣列與單次掃描的取捨，說明輸出空間、額外空間與迴圈不變量。

這篇筆記從原始實作出發，使用 AI 協助檢查推導與驗證案例。發布前重新核對了程式行為、複雜度與題目限制。

題目

對應原題：LeetCode 2574：Left and Right Sum Differences

給定整數陣列 nums，令 leftSum[i] 為索引 i 左側元素總和，rightSum[i] 為右側元素總和。回傳陣列 answer，其中 answer[i] = |leftSum[i] - rightSum[i]|。不存在的一側總和為 0。

例如 [10, 4, 8, 3] 的答案是 [15, 1, 11, 22]。

原始寫法正確，但保留了不需要的中間陣列

原始寫法先建立每個位置的左側和與右側和，最後才組出答案。

function leftRightDifference(nums: number[]): number[] {
  const total = nums.reduce((sum, num) => sum + num, 0);
  const leftSum = [0];
  const rightSum = [total - nums[0]];

  for (let index = 1; index < nums.length; index += 1) {
    leftSum.push(leftSum[index - 1] + nums[index - 1]);
    rightSum.push(total - nums[index] - leftSum[index]);
  }

  const answer: number[] = [];

  for (let index = 0; index < leftSum.length; index += 1) {
    answer.push(Math.abs(leftSum[index] - rightSum[index]));
  }

  return answer;
}

這個版本的答案正確。初始的 leftSum[0] 是 0，rightSum[0] 是第一個元素右邊的總和；後續每一格都依定義建立。

限制在於它同時保存 leftSum、rightSum 和 answer。三段線性掃描仍是 O(n) 時間，但即使不把回傳的 answer 算進去，兩個中間陣列也讓額外空間是 O(n)。原題只要最後的差值，沒有必要保留這兩份完整資料。

nums[0] 假設輸入至少有一個元素，這符合原題限制。若函式要當成通用工具，則需要另行定義空陣列應回傳什麼結果。

較佳方案：右側先扣掉當前值

先取得整體總和。迴圈中先把當前值從右側扣掉，再計算差值，最後把它加入左側。此時兩個變數都直接對應題目定義。

function leftRightDifference(nums: number[]): number[] {
  const answer: number[] = [];
  let leftSum = 0;
  let rightSum = nums.reduce((sum, num) => sum + num, 0);

  for (const num of nums) {
    rightSum -= num;
    answer.push(Math.abs(leftSum - rightSum));
    leftSum += num;
  }

  return answer;
}

常見的另一種寫法會先把 num 加入 leftSum，在扣除 rightSum 前就計算差值。它也正確，因為兩邊都包含同一個 num，相減時會抵銷。不過先扣右側、後加左側時，變數名稱在計算當下就等於題目中的左右總和，閱讀與說明都更直接。console.log() 只適合除錯，正式解答應移除。

為什麼正確

每次處理 num 前，leftSum 是已處理元素的總和，rightSum 是尚未處理元素加上 num 的總和。

先執行 rightSum -= num 後，rightSum 恰好是當前元素右側的總和；此時 leftSum 仍是左側總和，因此寫入的絕對差符合 answer 在目前索引的定義。再執行 leftSum += num，下一輪開始時不變量繼續成立。迴圈處理每個元素一次，因此所有索引都會得到正確結果。

最小驗證

import assert from "node:assert/strict";

assert.deepStrictEqual(leftRightDifference([10, 4, 8, 3]), [15, 1, 11, 22]);
assert.deepStrictEqual(leftRightDifference([1]), [0]);
assert.deepStrictEqual(leftRightDifference([5, -2, 4]), [2, 1, 3]);

第三組案例確認輸入含負數時，總和與絕對值仍依同一套規則運作。

複雜度與可遷移觀念

reduce() 計算總和一次，後續迴圈掃描一次，所以時間是 O(n)。answer 本身需要 O(n) 空間來回傳結果；若討論額外工作空間，這個方案只有兩個數值變數，是 O(1)。

原始版本的 leftSum 與 rightSum 在需要多次查詢所有前綴或後綴時仍有價值。這題只在每個索引寫入一次答案，保留它們只會增加記憶體用量。

常見陷阱

• 把目前元素同時排除或同時計入兩側，卻沒有確認公式是否抵銷。
• 沒有先確認 nums[0] 的前提，卻直接建立右側陣列。
• 把回傳陣列占用的空間和額外工作空間混為一談。
• 以 console.log() 取代 assertion，沒有在錯誤時失敗。

外部參考連結

• LeetCode 2574：Left and Right Sum Differences：原始題目、範例與限制。
• TypeScript Handbook：More on Functions：函式參數與回傳型別語法。
• Node.js：assert.deepStrictEqual()：以 assertion 驗證陣列結果。