LeetCode 238 詳解：Product of Array Except Self (除自身外數組乘積)

題目翻譯

給定長度為 n (n > 1) 的整數陣列 nums，返回陣列 output 使得 output[i] 等於除 nums[i] 以外所有元素的乘積。要求：

• 不使用除法
• 時間複雜度 O(n)
• 進階：空間複雜度 O(1)（輸出陣列不計入額外空間）

範例：輸入 [1,2,3,4] → 輸出 [24,12,8,6]

核心思路：前綴與後綴乘積

直接計算總乘積再除以各元素雖直觀，但違反「不使用除法」限制，且遇 0 值需特殊處理。標準解法採用左右乘積分解：

output[i] = (nums[0] × ... × nums[i-1]) × (nums[i+1] × ... × nums[n-1])

即 output[i] = leftProduct[i] × rightProduct[i]，其中：

• leftProduct[i] 為索引 i 左側所有元素乘積
• rightProduct[i] 為索引 i 右側所有元素乘積

O(1) 空間優化實作

利用輸出陣列直接存儲左乘積，再用單一變量累積右乘積：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> output(n, 1);
        
        // 正向遍歷：output[i] 存儲 nums[0] 到 nums[i-1] 的乘積
        for (int i = 1; i < n; ++i) {
            output[i] = output[i-1] * nums[i-1];
        }
        
        // 反向遍歷：用 right 累積右側乘積，直接乘到 output[i]
        int right = 1;
        for (int i = n - 1; i >= 0; --i) {
            output[i] *= right;
            right *= nums[i];
        }
        return output;
    }
};

關鍵點解析

複雜度分析

• 時間複雜度：O(n) — 兩次線性遍歷
• 空間複雜度：O(1) — 僅使用常數額外變量 right，輸出陣列不計入

為什麼不處理 0 值特殊情況？

左右乘積分解法天然處理 0 值：

• 單個 0：該位置輸出為其他元素乘積，其餘位置為 0
• 多個 0：所有位置輸出均為 0
• 無 0：正常計算

無需額外分支判斷，代碼更簡潔健壯。

總結

本題核心在於將「除自身外乘積」分解為「左乘積 × 右乘積」，並通過輸出陣列複用實現 O(1) 空間。此思想廣泛應用於陣列區間乘積/和問題，是陣列前綴後綴分解的經典範例。