題目目錄Product of Array Except Self

先乘左邊，再乘右邊，得到除了自己以外的乘積。

TIME O(n)輔助空間 O(1)，輸出 O(n)

01 / 兩趟累乘INITIALIZE

i—

prefix—

postfix—

nums 初始化

arr 每一格保存目前累乘結果

目前累積量包含的元素正在處理的索引 i

目前操作—先建立輸出陣列

先更新 arr[i]，再把 nums[i] 乘入累積量，因此不會把自己算進自己的答案；全程不使用除法。

STEP 01

速度

02 / 同步程式碼PYTHON

原理說明：為什麼先更新 arr[i]？

答案 = 左側乘積 × 右側乘積。

第一趟由左往右，更新 arr[i] 時，prefix 只包含 nums[0…i−1]。更新完成後，才將 nums[i] 納入 prefix，供下一格使用。

第二趟由右往左，更新 arr[i] 時，postfix 只包含 nums[i+1…n−1]。把它乘進已保存的左側乘積，就得到答案。

邊界外沒有元素時，乘積視為 1。負數與零都可以直接處理，不需要除法或特判。

原始演算法時間 O(n)，除輸出 arr 外的輔助空間 O(1)。動畫另外保存每一步的快照；數字使用整數精確運算。