0238. 除自身以外数组的乘积 #

标签：数组
难度：中等

题目大意 #

给定一个数组 nums。要求输出数组 output，其中 output[i] 为数组 nums 中除了 nums[i] 之外的其他所有元素乘积。

要求不能使用除法，且在 O(n) 时间复杂度、常数空间复杂度内解决问题。

解题思路 #

构造一个答案数组 res，长度和数组 nums 长度一致。先从左到右遍历一遍 nums 数组，将 nums[i] 左侧的元素乘积累积起来，存储到 res 数组中。再从右到左遍历一遍，将 nums[i] 右侧的元素乘积累积起来，再乘以原本 res[i] 的值，即为 nums 中除了 nums[i] 之外的其他所有元素乘积。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        res = [1 for _ in range(size)]

        left = 1
        for i in range(size):
            res[i] *= left
            left *= nums[i]

        right = 1
        for i in range(size-1, -1, -1):
            res[i] *= right
            right *= nums[i]
        return res