238. 除自身以外数组的乘积

https://leetcode-cn.com/problems/product-of-array-except-self/

解法一：

记录元素i左右乘积，再将对应的左右乘积相乘即可

时间o(n),空间o(n)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        #左右乘积，初始为1
        left = [1 for _ in range(n)]    
        right = [1 for _ in range(n)]
        #初始条件
        left[1] = nums[0]
        right[n-2] = nums[n-1]
        #正向求左侧乘积，反向求右侧乘积
        if n > 2:
            for i in range(2, n):
                left[i] = nums[i-1] * left[i-1]
            for j in range(n-3, -1, -1):
                right[j] = nums[j+1] * right[j+1]
        return [left[i] * right[i] for i in range(n)]

改进：

空间复杂度o（1）

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left = 1
        right = 1
        n = len(nums)
        res = [None for i in range(n)]
        for i in range(n):
            res[i] = left
            left *= nums[i] 
        for j in range(n-1, -1, -1):
            res[j] *= right
            right *= nums[j]        
        return res