原题

给定一个整数数组A。
定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。

样例
给出A=[1, 2, 3]，返回 B为[6, 3, 2]

解题思路

• 求出数组中每一个位置左边的乘积和右边的乘积
• 最后遍历每一个位置，把左右乘积相乘
• 时间复杂度O(n) - 扫两遍，或者可以扫三遍

完整代码

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        p = 1
        n = len(nums)
        output = []
        for i in range(0,n):
            output.append(p)
            p = p * nums[i]
        p = 1
        for i in range(n-1,-1,-1):
            output[i] = output[i] * p
            p = p * nums[i]
        return output