主題: 學習筆記

LeetCode 238：除自身以外陣列的乘積，從除法改成前綴與後綴

記錄我寫的除法版與前綴、後綴乘積版，釐清多個零、更新順序、正確性，以及 O(1) 額外空間與 O(n) 輸出空間的差別。

我第一個想到的是先算總乘積，再除以目前的數字。遇到零就另外處理。第二版改成先存右側乘積，再乘上左側乘積，整個過程不需要除法，也不必替零寫分支。

下面兩版都是我寫的解法。整理版只調整命名與型別，沒有另外換一套演算法。後面的正確性說明與測試是這篇文章補充的內容。

題目與限制

LeetCode 238：Product of Array Except Self 要求回傳每個位置以外所有元素的乘積。例如 [1, 2, 3, 4] 的答案是 [24, 12, 8, 6]，第一格是 2 × 3 × 4。

輸入長度介於 2 到 100000，元素介於 -30 到 30。題目保證任意前綴、後綴的乘積及答案都在 32 位元有號整數範圍內。正式要求是 O(n) 時間，而且不能使用除法；進階要求是 O(1) 額外空間，不計回傳陣列。

我最先寫的除法版

這裡把函式重新命名，方便與第二版放在一起比較。

function productExceptSelfWithDivision(nums: number[]): number[] {
    let hasZero = false;
    const total = nums.reduce((acc, b) => {
        if (b === 0 && !hasZero) {
            hasZero = true;
            return acc;
        } else {
            return acc * b;
        }
    }, 1);
    return nums.map(num => num === 0 ? total : hasZero ? 0 : total / num);
}

hasZero 的意思是已經遇過零。程式只跳過第一個零，第二個零仍會乘進 total。

在累積值保持有限數值時，這版並不是漏掉多個零。以 [-1, 0, 0, -3, 3] 為例，跳過第一個零後，第二個零仍讓累積值歸零。

但跳過零後的乘積不再是題目保證的前綴乘積。輸入 [0, ...new Array(220).fill(30), 0] 的每個前綴與後綴乘積都是零，答案也都是零，完全符合限制。

第一版跳過開頭的零後，卻會累積 30 的 220 次方，超出 JavaScript Number 的範圍成為 Infinity。最後乘上另一個零會得到 NaN。因此第一版除了違反除法限制，也有合法輸入會算錯。前面的分類表必須搭配有限數值這個前提。溢位行為可參考 MDN Infinity，下方測試則重現完整案例。

問題在於它使用了除法，不符合題目要求。這版的時間是 O(n)，額外空間 O(1)，回傳陣列占 O(n)。即使輸出符合範例，也不能忽略禁止除法的限制。

補充對照：每格重新相乘的暴力解

這不是我的第一版，而是補充的比對基準。固定位置 i，再走訪其他位置相乘，最容易直接對照題意。

function productExceptSelfBruteForce(nums: number[]): number[] {
    return nums.map((_, i) =>
        nums.reduce((product, value, j) => j === i ? product : product * value, 1)
    );
}

每格都重新算 n − 1 個元素，時間是 O(n²)。瓶頸是相鄰位置需要的乘積有大量重複計算。這段參考程式用於小範圍整數測試；任意跳過一個元素的中間乘積不一定受題目的前綴／後綴保證涵蓋，不能直接拿它當任意大數資料的精確性依據。

我改良的前綴與後綴版

我先從右邊走，讓每格存下自己右側的乘積，再從左邊走，乘上自己左側的乘積。以下保留原本的計算順序，只將 sufix 修正為 suffix，將 arr 改名為 answer，並補上陣列型別。

function productExceptSelf(nums: number[]): number[] {
    const answer = new Array<number>(nums.length);
    let suffix = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        answer[i] = suffix;
        suffix *= nums[i];
    }

    let prefix = 1;
    for (let i = 0; i < nums.length; i++) {
        answer[i] *= prefix;
        prefix *= nums[i];
    }
    return answer;
}

每個答案拆成兩部分：

answer[i] = 左側乘積 × 右側乘積

左右兩側都不包含 nums[i]。以 [1, 2, 3, 4] 為例：

最後一格右邊沒有元素，所以乘積是 1；第一格左邊也是如此。1 是乘法的單位元素，乘上它不會改變另一側的結果。若初始化成 0，所有累積值就會一直是零。

為什麼必須先使用，再更新

第一輪進入位置 i 時，suffix 恰好等於 i 右側所有元素的乘積。

先把它寫進 answer[i]，再乘上 nums[i]，就得到下一輪位置需要的右側乘積。起點在最右側，右邊沒有元素，初始值 1 符合定義。依照這個順序往左走，每格存下的值都不包含自己。

第二輪進入位置 i 時，prefix 恰好等於 i 左側所有元素的乘積。此時 answer[i] 還保存右側乘積，兩者相乘剛好涵蓋除了 i 以外的每個位置，而且各乘一次。接著更新 prefix，留給下一格使用。

若先執行 prefix *= nums[i] 才更新答案，就會把自己也乘進去。同樣地，第一輪也不能顛倒更新順序。

零不需要特殊處理。只有一個零時，只有零所在的位置能避開它；有兩個零時，排除任何一個位置後仍有零，所以答案全部為零。

空間 O(1) 到底算了什麼

第二版走訪陣列兩次，每次 O(n)，合起來仍是 O(n)。它必須產生 n 個輸出值，所以在這個計算模型下，O(n) 時間已符合輸出本身的需求。

prefix、suffix 與索引只占固定數量的變數，額外空間是 O(1)。answer 有 n 格，輸出空間是 O(n)，包含輸出的總空間也就是 O(n)。第一版也是這個空間分類，第二版的改進是移除除法與零值分支，不是把輸出陣列省掉。

不需要再建立完整的左右乘積陣列，也不需要改寫成兩個方向同時更新的單一迴圈。現在的兩輪分工已經能直接對照正確性說明。

可執行測試

把兩版函式與以下程式放在同一個 TypeScript 檔案，以支援 TypeScript 的執行環境執行。測試也確認輸入陣列沒有被修改，最後一項則重現第一版的溢位問題。

import assert from "node:assert/strict";

function check(nums: number[], expected: number[]): void {
    const original = [...nums];
    const actual = productExceptSelf(nums);
    assert.equal(actual.length, expected.length);
    actual.forEach((value, i) => assert.ok(value === expected[i]));
    assert.deepStrictEqual(nums, original);
}

check([1, 2, 3, 4], [24, 12, 8, 6]);
check([-1, 1, 0, -3, 3], [0, 0, 9, 0, 0]);
check([-1, 0, 0, -3, 3], [0, 0, 0, 0, 0]);
check([2, 3], [3, 2]);
check([-1, -2, -3], [6, 3, 2]);
check([0, 0], [0, 0]);
check([0, ...new Array(220).fill(30), 0], new Array(222).fill(0));
assert.ok(productExceptSelfWithDivision([0, ...new Array(220).fill(30), 0]).some(Number.isNaN));

JavaScript 的乘法可能產生 -0。=== 將它與 0 視為相等，但 Node.js 嚴格斷言會區分正負零。因此這裡先檢查長度，再逐格使用數值相等比較；輸入是否改動則用 deepStrictEqual 檢查。這是測試比較方式的選擇，不必為了顯示成 0 而修改演算法。Node.js 斷言文件

另外以長度 2 到 6、元素為 -2 到 2 的 19525 組陣列，將兩版與暴力解比對，正規化正負零後結果一致。這是有限範圍驗證，不取代前面的正確性論證，也不代表除法版符合題目限制。

這題留下的觀念

「除了自己」可以拆成左右兩側，累積結果不必每次重算。寫迴圈時，先說清楚變數在進入這一輪時代表哪些元素，再決定何時更新，比只記住程式順序更容易檢查錯誤。

這次第二版已經滿足線性時間與固定額外空間。後續要練的是能自行說明兩輪的不變量，並把案例寫成真的會失敗的測試。

參考資料

• LeetCode 238：Product of Array Except Self：題意、限制與額外空間的計算方式。
• Node.js assert：斷言與正負零的比較行為。
• MDN Infinity：超出數值範圍的運算結果。