Product of Array Except Self

題目描述

給定整數陣列 nums，回傳陣列 answer，其中 answer[i] 等於 nums 中除了 nums[i] 以外所有元素的乘積。不能使用除法，且要求 O(n) 時間。

輸入：nums = [1,2,3,4]
輸出：[24,12,8,6]

輸入：nums = [-1,1,0,-3,3]
輸出：[0,0,9,0,0]

解題思路

前綴積

從左到右遍歷，answer[i] 存放 nums[0]×nums[1]×...×nums[i-1]，answer[0]=1（左邊沒有元素）

後綴積

從右到左遍歷，用變數 suffix 累積 nums[i+1]×...×nums[n-1]，每步將 answer[i] 乘上 suffix

合併

兩次遍歷後 answer[i] = 左邊所有元素乘積 × 右邊所有元素乘積，恰好跳過 nums[i]

程式碼

C#

csharp

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] answer = new int[n];
 
        // 前綴積：answer[i] 先存左邊的累積乘積
        answer[0] = 1;
        for (int i = 1; i < n; i++)
            answer[i] = answer[i - 1] * nums[i - 1];
 
        // 後綴積：用一個變數從右邊累積，乘進 answer
        int suffix = 1;
        for (int i = n - 2; i >= 0; i--) {
            suffix *= nums[i + 1];
            answer[i] *= suffix;
        }
        return answer;
    }
}

TypeScript

typescript

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const answer = new Array(n);
 
    // 前綴積
    answer[0] = 1;
    for (let i = 1; i < n; i++)
        answer[i] = answer[i - 1] * nums[i - 1];
 
    // 後綴積
    let suffix = 1;
    for (let i = n - 2; i >= 0; i--) {
        suffix *= nums[i + 1];
        answer[i] *= suffix;
    }
    return answer;
}

Python

python

def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    answer = [1] * n
 
    # 前綴積
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
 
    # 後綴積
    suffix = 1
    for i in range(n - 2, -1, -1):
        suffix *= nums[i + 1]
        answer[i] *= suffix
 
    return answer

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |

第一次從左到右遍歷 O(n) 建前綴積，第二次從右到左遍歷 O(n) 乘後綴積，合計 O(2n) = O(n)。輸出陣列是題目要求的回傳值不計入額外空間，只用一個 suffix 變數，空間 O(1)。

邊界情況

陣列包含一個 0：只有 0 所在位置的 answer 不為 0（等於其他元素的乘積），其餘位置因為乘到 0 而全部是 0
陣列包含多個 0：所有位置的 answer 都是 0，因為無論哪個位置，其他元素中至少有一個 0
陣列包含負數：演算法不受影響，負負得正由乘法自動處理

圖解

nums: [1,2,3,4]

左→右→

前綴積: [1,1,2,6]

相乘→

後綴積: [24,12,4,1]

相乘→

answer: [24,12,8,6]

圖表展示 [1,2,3,4] 的兩趟掃描。前綴積 [1,1,2,6] 表示：index 0 左邊沒有元素（1），index 1 左邊是 1，index 2 左邊乘積是 1x2=2，index 3 是 1x2x3=6。後綴積同理從右算起。兩者對應位置相乘得到最終答案。

進階觀點

💡面試追問

為什麼不能用除法？ 題目明確禁止。即使允許，陣列含 0 時會除以零。需要分三種情況處理：零個 0（正常除法）、一個 0（只有 0 的位置有非零結果）、多個 0（全部為 0）。邏輯複雜且容易出錯。
如果允許除法？ 先算全部乘積 P，answer[i] = P / nums[i]。但必須特別處理上述 0 的三種情況，面試時容易遺漏邊界。
這個前綴/後綴技巧還能用在哪？ Trapping Rain Water（前綴最大高度 × 後綴最大高度）、Range Sum Query（前綴和查詢區間和）都使用類似的「預計算左右兩側資訊」策略。

理解測驗

🤔 為什麼 answer[i] = prefix[i] × suffix[i] 就是除自身外的乘積？

🤔 nums = [0, 1, 2] 時，answer 是什麼？