238. Product of Array Except Self

題目 / Problem

中文 給定一個整數陣列 nums，回傳一個陣列 answer，其中 answer[i] 等於 nums 中除了 nums[i] 之外所有元素的乘積。

• 題目保證 nums 任何前綴或後綴的乘積都能放入 32-bit 整數。
• 必須在 O(n) 時間內完成，且不能使用除法。
• 進階：能否做到 O(1) 額外空間？（輸出陣列不算額外空間。）

English Given an integer array nums, return an array answer such that answer[i] equals the product of every element of nums except nums[i].

• The product of any prefix or suffix is guaranteed to fit in a 32-bit integer.
• Must run in O(n) time and must not use division.
• Follow-up: can you achieve O(1) extra space (the output array doesn't count)?

Constraints - 2 <= nums.length <= 10^5 - -30 <= nums[i] <= 30 - Each answer[i] fits in a 32-bit integer.

Worked example - Input: nums = [1,2,3,4] - Output: [24,12,8,6] - 解釋 / Explanation: answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, answer[2] = 1*2*4 = 8, answer[3] = 1*2*3 = 6.

名詞解釋 / Glossary

• 前綴乘積 / Prefix product: 從陣列最左端到某位置（不含該位置）的所有元素相乘。例如 nums=[1,2,3,4] 在索引 2 的前綴乘積是 1*2 = 2。Useful because answer[i] = prefix product at i × suffix product at i.
• 後綴乘積 / Suffix product: 從某位置（不含該位置）到陣列最右端的所有元素相乘。Mirror image of the prefix product.
• 原地修改 / In-place: 不另外配置與輸入大小成比例的記憶體，而是在既有陣列上覆寫。Helps achieve O(1) extra space (output array excluded).
• O(n) / 線性時間: 執行步數隨輸入大小線性成長；本題禁止使用 O(n^2) 的雙重迴圈或除法捷徑。
• 指標 / Pointer (C): A variable holding a memory address. int* p means p stores the address of an int; *p reads/writes the value at that address. Used by LeetCode's C signature to return both the array and its length.
• malloc / 動態配置: malloc(n * sizeof(int)) 在堆積（heap）上要求 n 個整數的空間並回傳指標。LeetCode 會自行 free 該指標，所以我們不在解中呼叫 free。
• std::vector<int> (C++): 可動態調整大小的陣列容器，類似 Python 的 list。vector<int> v(n, 1) 建立長度 n、每格初始為 1 的向量。

思路

最直覺的暴力解是對每個 i 掃過整個陣列，把除了 nums[i] 之外的元素乘起來，這需要 O(n^2) 時間，當 n = 10^5 時太慢。另一個取巧的方法是先算出全體乘積再除以 nums[i]，但題目明確禁止除法，而且當陣列含有 0 時除法本身也會出錯。關鍵觀察是：answer[i] 可拆成「i 左邊所有元素的乘積」乘上「i 右邊所有元素的乘積」，這兩部分可以用一次線性掃描各自累積。第一次從左到右掃，把目前累積的左邊乘積寫入 answer[i]，再更新累積值；第二次從右到左掃，用一個變數 right 紀錄右邊累積乘積，把 answer[i] *= right 後再更新 right。這樣兩次線性掃描就完成，且只用了一個額外變數，達到 O(1) 額外空間（不計輸出）。

The brute force computes each answer[i] by re-multiplying the other n-1 elements, costing O(n^2) — too slow for n = 10^5. Dividing the total product by nums[i] is forbidden and also breaks when any nums[i] = 0. The key insight is that answer[i] factors cleanly into the product of everything to the left of i times the product of everything to the right of i. We can build both with prefix/suffix sweeps. Pass 1 walks left-to-right, writing the running left-side product into answer[i] before multiplying nums[i] into the running product — this guarantees answer[i] excludes nums[i] itself. Pass 2 walks right-to-left with a single scalar right, multiplying it into answer[i] and then folding nums[i] into right. Two linear passes, one extra variable, no division — O(n) time, O(1) extra space.

逐步走查 / Walkthrough

Input: nums = [1, 2, 3, 4], n = 4.

Pass 1 (left → right): 用 left 累積左邊乘積，先寫入 answer[i]，再乘上 nums[i]。

After Pass 1: answer = [1, 1, 2, 6] (left-side products).

Pass 2 (right → left): 用 right 累積右邊乘積，先乘進 answer[i]，再乘上 nums[i]。 Start with right = 1.

Final: answer = [24, 12, 8, 6] ✅

關鍵不變式 / Key invariant: 在第 i 次迭代「寫入」前，left（或 right）剛好等於「索引 i 左邊（或右邊）所有元素的乘積」，所以 answer[i] 永遠不會把 nums[i] 自己乘進去。

Solution — C

/*
 * Algorithm: two linear sweeps over nums.
 * 演算法：對 nums 進行兩次線性掃描。
 * Pass 1 fills answer[i] with the product of everything to the LEFT of i.
 * Pass 2 multiplies in the product of everything to the RIGHT of i, using one scalar.
 * 第一次掃描把 i 左邊的乘積放入 answer[i]，第二次掃描再乘上 i 右邊的乘積。
 * Result: O(n) time, O(1) extra space (excluding the returned output array).
 */

/* LeetCode's C signature returns a heap-allocated int* and writes the length via a pointer. */
/* LeetCode 的 C 介面回傳一個動態配置的 int*，並透過指標把長度寫回呼叫端。 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    /* Tell the caller the output length equals the input length. */
    /* 告訴呼叫端輸出長度等於輸入長度。 */
    *returnSize = numsSize;

    /* malloc allocates numsSize ints on the heap; LeetCode frees this for us. */
    /* malloc 在堆積上配置 numsSize 個 int 的空間；LeetCode 會自行釋放。 */
    int* answer = (int*)malloc(sizeof(int) * numsSize);

    /* Pass 1: build prefix (left-side) products into answer[]. */
    /* 第一次掃描：把每個位置左邊的乘積寫入 answer[]。 */
    int left = 1;                         /* left = product of nums[0..i-1] / 目前 i 左邊累積乘積 */
    for (int i = 0; i < numsSize; i++) {
        answer[i] = left;                 /* write BEFORE updating, so nums[i] itself is excluded / 先寫入再更新，排除自己 */
        left *= nums[i];                  /* fold nums[i] into the running left product / 把 nums[i] 併入累積乘積 */
    }

    /* Pass 2: walk right-to-left, multiplying in suffix (right-side) products. */
    /* 第二次掃描：從右往左，把右邊乘積乘進 answer[]。 */
    int right = 1;                        /* right = product of nums[i+1..n-1] / 目前 i 右邊累積乘積 */
    for (int i = numsSize - 1; i >= 0; i--) {
        answer[i] *= right;               /* combine left product (already in answer[i]) with right product / 結合左、右乘積 */
        right *= nums[i];                 /* fold nums[i] into the running right product / 把 nums[i] 併入右側累積乘積 */
    }

    /* answer now holds the final products; return the heap pointer. */
    /* answer 已經是最終答案；回傳這個堆積指標。 */
    return answer;
}

Solution — C++

/*
 * Same two-pass algorithm, idiomatic C++ with std::vector.
 * 相同的兩次掃描演算法，使用 std::vector 寫成符合 C++ 慣例的版本。
 * Pass 1: answer[i] = product of nums to the LEFT of i.
 * Pass 2: multiply in the product of nums to the RIGHT of i using a single scalar.
 * 時間 O(n)、額外空間 O(1)（不計輸出向量）。
 */
class Solution {
public:
    /* vector<int> is a dynamically-sized array container; passed by const reference for efficiency. */
    /* vector<int> 是可動態調整大小的陣列容器；用 const 參考傳入避免複製。 */
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();              /* n = number of elements / 元素個數 */

        /* Construct the output vector of length n, every slot pre-initialized to 1. */
        /* 建立長度為 n 的輸出向量，每格初始化為 1（乘法單位元）。 */
        vector<int> answer(n, 1);

        /* Pass 1: left-to-right sweep building prefix products into answer. */
        /* 第一次掃描：由左至右建立前綴乘積。 */
        int left = 1;                     /* running product of nums[0..i-1] / i 左邊累積乘積 */
        for (int i = 0; i < n; ++i) {
            answer[i] = left;             /* write the current left product BEFORE folding in nums[i] / 先寫入再更新 */
            left *= nums[i];              /* update the running left product / 更新左側累積乘積 */
        }

        /* Pass 2: right-to-left sweep multiplying in suffix products. */
        /* 第二次掃描：由右至左乘上後綴乘積。 */
        int right = 1;                    /* running product of nums[i+1..n-1] / i 右邊累積乘積 */
        for (int i = n - 1; i >= 0; --i) {
            answer[i] *= right;           /* combine left (already stored) and right products / 結合左右兩側乘積 */
            right *= nums[i];             /* update the running right product / 更新右側累積乘積 */
        }

        /* Return by value; modern C++ moves the vector out cheaply (no full copy). */
        /* 以值回傳；現代 C++ 會以 move 高效轉移，不會整份複製。 */
        return answer;
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只做了兩次長度為 n 的迴圈，每次迭代裡只有常數次乘法與賦值，所以總步數是 2n，去掉常數即 O(n)。n 是 nums 的長度。 / Two passes of length n, each iteration is constant work, so total is 2n = O(n) where n = nums.size().
• Space: O(1) 額外空間（不含輸出）— 我們只用了 left、right、i 等常數個整數變數；輸出陣列依題目規定不計入額外空間。 / Only a couple of scalar integers (left, right, the loop index) beyond the required output array, which the problem explicitly excludes.

Pitfalls & Edge Cases

• 想用除法 / Reaching for division: 全乘積除以 nums[i] 看似簡單，但題目禁止，且當 nums 含 0 時會除以 0 或得到錯誤結果。前後綴乘積法天生就能處理零。 / Total-product ÷ nums[i] is forbidden and breaks on zeros (division by zero, wrong values when there are 1+ zeros). Prefix/suffix products handle zeros naturally.
• 寫入順序 / Write-then-update order: 在迴圈內必須先 answer[i] = left; 再 left *= nums[i];。如果順序顛倒，left 就會把 nums[i] 自己也乘進去，違反「except self」。 / Inside the loop you must write answer[i] before folding nums[i] into left/right; otherwise you accidentally include nums[i] itself.
• 零的處理 / Multiple zeros: 例如 [-1,1,0,-3,3]，含一個 0 時只有 0 所在那格非零；含兩個以上 0 時答案全為 0。前後綴掃描自動正確處理，不需特判。 / With one zero only that index is non-zero; with two-plus zeros every output is 0. The two-pass method handles this without special casing.
• 以為要用 long long / Worrying about overflow: 題目保證任何前後綴乘積都裝得下 32-bit int，所以 int 已足夠，不必升級為 long long。 / Problem guarantees prefix/suffix products fit in 32-bit, so int is safe; no need for long long.
• C 版本的 returnSize / Forgetting *returnSize: LeetCode 的 C 介面靠 *returnSize = numsSize; 知道輸出長度，漏寫會讓判題器讀到隨機長度。 / In LeetCode's C harness you must set *returnSize; forgetting it leaves the grader reading garbage length.
• 誤把輸出計入空間 / Counting the output as extra space: 進階要求是 O(1) 額外 空間，輸出陣列本來就必須建立，不算進去。 / The follow-up's O(1) budget excludes the required output array — don't try to "save" it.