分析

将某个元素左边所有元素相乘 * 右边所有元素相乘返回即可

Python 超时版

16/17 有个超长的列表又尼玛超时了。。。
Time O(n^2)
Space O(n)

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nn = []
        for i in range(len(nums)):
            nn.append(self.pro(nums, 0, i) * self.pro(nums, i+1, len(nums)))
        return nn
    
    def pro(self, nums, start, end):
        s = 1
        for i in range(start, end):
            s *= nums[i]
        return s

继续分析

假设有一个列表pro_before = [..pro(nums, 0, i)..]
有个列表pro_after = [...pro(nums, i, len(nums)..]
那么本题的解为pro_before[i] * pro_after[i]
而上述两个列表只需要正向反向扫描nums即可
这样只有线性扫描 Time O(n)
注意这里pro_before * pro_after 所以实际上都是连乘在里面所以不需要开两个数组
只需要初始化res为全1的数组即可
Space O(n)

image.png

Python

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [1] * len(nums)
        t = 1
        for i in range(len(nums)):
            res[i] *= t
            t *= nums[i]
        t = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= t
            t *= nums[i]
        return res