LeetCode 238: Product of Array Except Self

第一眼看到這題時，我的初步想法是：「全部乘起來再除以自己應該就好了。」

然後就看到題目寫著 without using the division operation，只能想別的方法了。

題目

題目連結：LeetCode 238. Product of Array Except Self

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

Example:

• Input: nums = [1, 2, 3, 4]
• Output: [24, 12, 8, 6]

限制有兩條：不能用除法，時間複雜度要 $O(n)$。

除法為什麼不行

先說那個無法使用的方法：

$answer[i] = \frac{TotalProduct}{nums[i]}$

除了題目不讓用以外，主要也是因為如果陣列裡有 0，會直接炸掉。雖然可以特別處理零的情況，但邏輯會變得很瑣碎，而且已經違反規則了，所以就不糾結了。

拆成左邊和右邊

對任意位置 i 來說，answer[i] 其實就是它 左邊所有數的乘積 ($L[i]$) 乘上 右邊所有數的乘積 ($R[i]$)：

$answer[i] = L[i] \times R[i]$

拿 nums = [1, 2, 3, 4] 的 nums[2]（數值 3）來看：

左邊是 [1, 2]，乘積 2；右邊是 [4]，乘積 4。答案就是 $2 \times 4 = 8$。

發現這點之後，剩下的就是怎麼有效率地把左右兩邊的乘積算出來。

Two-Pass 做法

做兩趟就夠了：

1. 從左掃到右：一邊走一邊累積左邊的乘積，存進 answer。
2. 從右掃到左：一邊走一邊累積右邊的乘積，直接乘進 answer。

這樣不需要額外開兩個陣列，空間就省下來了。

直接跟著跑一次：

Table: 實際走訪過程

最後答案就是 [24, 12, 8, 6]。

程式碼

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n
        
        # 從左到右，累積左邊的乘積
        left = 1
        for i in range(n):
            answer[i] = left
            left *= nums[i]
            
        # 從右到左，把右邊的乘積乘進去
        right = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right
            right *= nums[i]
            
        return answer

重點在於 left 和 right 兩個變數就是滾動的累積器，走過每個位置時先把當前累積值交出去，再把 nums[i] 吃進來給下一個位置用。不需要額外開 left_array 或 right_array。

複雜度

• Time: $O(n)$。兩趟遍歷，都是線性。
• Space: $O(1)$（不算 output 的 answer）。只用了 left 和 right 兩個變數。

小結

這題本質上是 Prefix 技巧的變體，只是把加法改成乘法。

類似的「左右各掃一趟」技巧在其他題目也常出現，像是 42. Trapping Rain Water 也能用類似的思路處理。如果這題解順了，可以接著試試看那題。