題意

給定一個數組a[]，對于其中的每一個元素x，求數組中所有數相乘并除以該元素x的結果。并且不能使用除法。

思路

算法1

O(n)$O(n)$時間和O(n)$O(n)$空間。

我們維護一個l[i]和r[i]數組，分別代表從左往右乘到元素ai$a_i$的積和從右往左乘到元素ai$a_i$的積。

那么，對于我們要求的結果ansi=li?1?ri+1$ans_i = l_{i - 1} · r_{i + 1}$。

算法2

O(n)$O(n)$時間和O(1)$O(1)$空間。

我們需要想辦法去優化一下空間，其實從我們上面的式子ansi=li?1?ri+1$ans_i = l_{i - 1} /cdot r_{i+1}$就可以發現：我們的li$l_i$是可以從左向右遞推得到的，我們的ri$r_i$也可以從右向左遞推得到，并且在遞推過程中，我們的l和r其實不用用數組保存。

那么我們只需要從左往右遍歷一遍得到ansi=li?1$ans_i = l_{i-1}$，然后再從右往左遍歷一遍得到ansi=ansi?ri+1$ans_i = ans_i * r_{i + 1}$即可。

代碼