數組剔除元素後的乘積

題目描述：給定一個整數數組A。定義B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 計算B的時候請不要使用除法。

樣例：給出A=[1, 2, 3]，傳回 B為[6, 3, 2]

最直覺的方法就是寫兩層循環，第一層周遊n個位置（n是數組長度），第二層周遊除了這個位置的元素之外的所有元素，計算乘積。這樣做的時間複雜度為O(n^2);

這樣當然是能實作的。不過如果就是這樣，我在這裡也就沒必要專門講解這個問題了。這道題還有一種時間複雜度為O(n)的算法，那就是通過犧牲空間複雜度換取時間上的高效。

求的是數組除了i位之外所有元素的乘積，那麼可以将數組看成兩個部分：一部分是在i之前的，一部分是在i之後的。這兩個部分各自的乘積再乘起來就是最終的答案。

是以，可以開辟兩個數組的空間，一部分存每個i位左邊的所有元素的乘積，一個存i位右邊的。這樣的兩個數組通過周遊原數組兩邊就可以得到。最後再将這兩個數組對應位乘起來，得到最終的結果。

代碼如下：

class Solution:
    """
    @param A: Given an integers array A
    @return: An integer array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
    """
    def productExcludeItself(self, A):
        left, right = [1], [1]
        result = []
        for i in A[:-1]:
            left.append(left[-1] * i)
        for i in A[-1:0:-1]:
            right.append(right[-1] * i)
        index = 0
        n = len(A)
        while index < n:
            result.append(left[index] * right[n - 1 - index])
            index += 1
        return result
        # write your code here