主題: 學習筆記

LeetCode 1480：TypeScript 一維陣列累積總和

用前一格已累積的值完成單次掃描，說明原地修改、迴圈不變量與 O(n) 時間複雜度。

累積總和看起來很小，卻很適合練習迴圈中的狀態。從第二格開始，前一格已經是目前為止的總和。把它加到當前值，就得到新的累積總和。

題目

對應原題：LeetCode 1480：Running Sum of 1d Array

給定整數陣列 nums，回傳一個陣列。索引 i 的值等於 nums[0] 到 nums[i] 的總和。

例如，[1, 2, 3, 4] 的結果是 [1, 3, 6, 10]。

先看會重複計算的作法

最直接的想法是，對每個索引重新加總前面的所有數字。

function runningSumNaive(nums: number[]): number[] {
  return nums.map((_, end) => {
    let sum = 0;

    for (let start = 0; start <= end; start += 1) {
      sum += nums[start];
    }

    return sum;
  });
}

這會反覆計算相同的前綴。第一格加一次，第二格再加前兩個值，依此類推，總時間是 O(n²)。

把前一格當成累積狀態

前一格已保留前綴總和，因此不必從頭重算。直接更新目前這一格即可。

function runningSum(nums: number[]): number[] {
  for (let index = 1; index < nums.length; index += 1) {
    nums[index] += nums[index - 1];
  }

  return nums;
}

這個版本會直接改動 nums，並回傳同一個陣列。原題只要求回傳累積總和；若呼叫端還需要原始資料，先複製陣列再呼叫函式。

為什麼正確

在每次迴圈開始時，索引小於 index 的每一格都已經是對應位置的累積總和。

基礎情況是 index = 1。nums[0] 沒有改動，正好是第一個元素的累積總和。執行 nums[index] += nums[index - 1] 後，當前值會變成原始 nums[index] 加上前一格的累積總和，也就是從索引 0 加到 index 的總和。迴圈結束時，每一格都符合題目定義。

最小驗證

console.log() 只能讓人目視結果。使用 assertion，結果不符時會直接失敗。

import assert from "node:assert/strict";

assert.deepStrictEqual(runningSum([1, 2, 3, 4]), [1, 3, 6, 10]);
assert.deepStrictEqual(runningSum([3, 1, 2, 10, 1]), [3, 4, 6, 16, 17]);
assert.deepStrictEqual(runningSum([-2, 5, -1]), [-2, 3, 2]);

複雜度與取捨

迴圈只走過陣列一次，時間是 O(n)。這個版本沒有建立新的工作陣列，額外空間是 O(1)，但代價是修改輸入。

若要保留輸入，可先寫 const result = [...nums]，再對 result 執行同樣的迴圈。時間仍是 O(n)，額外空間則改為 O(n)。

常見陷阱

• 從索引 0 開始，讀取不存在的前一格。
• 對每個位置重新從頭加總，讓時間退化成 O(n²)。
• 沒有說明函式會改動輸入，讓呼叫端誤以為原陣列保持不變。
• 把回傳陣列占用的空間和額外工作空間混在一起討論。

可遷移的觀念

這題的狀態是前一格的累積總和。只需要最後總和時，用一個變數即可；需要保留每個位置的結果時，才把狀態寫回陣列。這個差別會延伸到 prefix sum、區間查詢與許多動態規劃題目。

外部參考連結

• LeetCode 1480：Running Sum of 1d Array：原始題目、範例與限制。
• TypeScript Handbook：More on Functions：函式參數與回傳型別語法。
• Node.js：assert.deepStrictEqual()：使用嚴格深層比較驗證陣列結果。