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

image.png

分析

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

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