Product of Array Except Self

• 题目描述
• 方法
• 参考

题目描述

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

方法

可以发现每个位置其实都是它前面所有数的乘积再乘上它后面所有数的乘积。按照这种想法建立返回数组，首先该数组中从第二个数开始每个数都是前面数的乘积，这样完成了第一步，其实此时数组中的最后一个数已经是返回值了。接下来从返回数组的倒数第二个数开始向前，每个返回值都是该数字（也就是nums中该数以前数的乘积）与nums该数字以后数字乘积的乘积。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        temp = 1
        res = []
        res.append(1)
        for i in range(len(nums)-1):
            temp *= nums[i]
            res.append(temp)
        temp = 1
        for i in range(len(nums)-2,-1,-1):
            temp *= nums[i+1]
            res[i] *= temp
        return res

参考

• leetcode 【238 Product of Array Except Self】【Python】