Sofie 舒霏的部落格

今天要來解的題目是 Leetcode－238. Product of Array Except Self，難度為 Medium，

而我所使用的語言是 python3

壹、理解題目

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

Example 1:

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

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Note:

• Could you solve it in O(n) time complexity and without using division?
• Could you solve it with O(1) constant space complexity? (The output array does not count as extra space for space complexity analysis.)

要如何只用 O(n) 的時間複雜度，而且除了 answer array，只用到 O(1) 的空間複雜度呢？

貳、解題！

想要得到「除了自己以外的乘積」，

可以從左掃過來，得到左邊的乘積們，接著再從右掃回來，把先前得到的乘積們，再乘上右邊掃過來的乘積。

《圖解時間》

首先，從左邊掃過去，得到第二列的結果。

舉例來說， 6 = 1 x 2 x 3，就代表著「4」以左的所有數字 (1, 2, 3) 相乘。

有了「以左的所有數字乘積」後，還缺右邊的數字乘積。

所以，我們需要從右邊掃回來：

用一個變數 (n) 紀錄目前「以右的乘積」（在下圖中 n = 4） ，

並且更新 answer array，也就是 n x ans[i]

TADA! 這樣就建構完成了！