題目描述:給定整數陣列 nums,回傳陣列 answer,其中 answer[i] 是 nums 中除 nums[i] 以外所有元素的乘積,且不能使用除法。
解題思路:對每個位置 i,答案等於「i 左側所有元素的乘積」×「i 右側所有元素的乘積」。先做一次左掃(前綴積),再做一次右掃(後綴積)。具體做法:先用 output[i] 存 i 左側的前綴積,再用一個變數 right 從右往左乘入後綴積,這樣只需兩次線性掃描、O(1) 額外空間(輸出陣列不計)。
時間複雜度:O(n) — 兩次線性掃描。
空間複雜度:O(1) 額外空間 — 輸出陣列不計入,只用兩個乘積變數。
1. Initialize output array of size n with all 1s 2. Left pass: track running product from left - output[i] = left; left *= nums[i] 3. Right pass: track running product from right - output[i] *= right; right *= nums[i] 4. Return output
使用除法(不允許):計算總乘積,再除以各元素。在出現零時失效。
前綴和後綴陣列 O(n) 空間:顯式存儲前綴和後綴乘積陣列,再相乘。時間複雜度相同但額外空間為 O(n) — 雙重掃描原地方法更優。