LeetCode 238 Product of Array Except Self —— 前後綴乘積 O(n) 無除法解法

LeetCode 238 要求：給定長度 n > 1 的整數陣列 nums，構建輸出陣列 output 使 output[i] 等於除 nums[i] 外所有元素的乘積。不能使用除法，時間 O(n)，進階要求 O(1) 額外空間（輸出陣列不算額外空間）。

一、核心思想：前綴乘積 × 後綴乘積

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

定義兩個輔助陣列：

• left[i] = nums[0] × ... × nums[i]（含自身）
• right[i] = nums[i] × ... × nums[n-1]（含自身）

則 output[i] = left[i-1] × right[i+1]（邊界單獨處理）。

二、標準三次遍歷版（易懂，O(n) 空間）

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] left = new int[n], right = new int[n], ans = new int[n];

    left[0] = nums[0];
    for (int i = 1; i < n; ++i) left[i] = left[i-1] * nums[i];

    right[n-1] = nums[n-1];
    for (int i = n-2; i >= 0; --i) right[i] = right[i+1] * nums[i];

    ans[0] = right[1];
    ans[n-1] = left[n-2];
    for (int i = 1; i < n-1; ++i) ans[i] = left[i-1] * right[i+1];

    return ans;
}

三、進階 O(1) 空間版（輸出陣列複用）

用 ans 直接存儲 left，再反向累乘 right：

vector productExceptSelf(vector& nums) {
    int n = nums.size();
    vector ans(n, 1);

    // 正向：ans[i] 存 nums[0]~nums[i-1] 的乘積
    for (int i = 1; i < n; ++i)
        ans[i] = ans[i-1] * nums[i-1];

    // 反向：用變量 right 累乘 nums[i+1]~nums[n-1]
    int right = 1;
    for (int i = n-1; i >= 0; --i) {
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
}

四、示例演示

Input:  [1, 2, 3, 4]
left :  [1, 1, 2, 6]   // ans 正向後
right:       [24,12,4,1] // 反向累乘變量
Output: [24, 12, 8, 6]

五、關鍵點總結

1. 「不含自身」的乘積拆解為「左側乘積」×「右側乘積」。
2. 進階版利用輸出陣列存左側乘積，單變量滾動右側乘積，達到 O(1) 額外空間。
3. 注意整數溢位：題目未給模數，實際工程中可用 long long 或取模。