Problem#
給你一個整數陣列 nums，要你回傳答案陣列 answer[i] = nums[0] * ... * nums[i-1] * nums[i+1] * ... * nums[n-1] (也就是除了 nums[i] 之外的相乘）
時間複雜度必須在 $O(n)$。
測資限制#
- $2 \le n \le 10^5$
- $-30 \le val \le 30$
想法#
先算好全部相乘，對於 answer[i] 的計算，可以是 total / nums[i]，這樣一來就可以不用每次都去重算 0 ~ n-1 除去 i 的乘積了。
唯一的例外就是只有出現一個 0 的狀況（如果出現兩個以上的 0 則答案都是 0)，只有 nums[i] == 0 的 answer[i] 會有值，其他都是 0，因為只有 answer[i] 不會乘到 0 (除了自己之外）
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(n)$