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

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
本站总访问量  次  |  您是本站第  位访问者