LeetCode-238. 除自身以外数组的乘积【数组 前缀和】（清晰图解）_图解leetcode——238

题目描述：

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

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

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

解题思路一：乘积 = 当前数左边的乘积 * 当前数右边的乘积

1, 2, 3, 4
pre_mult = 1,2,4,24
last_mult = 24,24,12,4
更新后
pre_mult = 1,1,2,4
last_mult = 24,12,4,1

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        pre_mult = []
        last_mult = []
        cur = 1
        for i in range(len(nums)):
            cur *= nums[i]
            pre_mult.append(cur)
        cur = 1
        for i in range(len(nums)-1, -1, -1):
            cur *= nums[i]
            last_mult.append(cur)
        last_mult = last_mult[::-1]
        result = []
        for i in range(len(nums)):
            if i == 0:
                result.append(last_mult[i+1])
            elif i == len(nums) -1:
                result.append(pre_mult[i-1])
            else:
                result.append(pre_mult[i-1] * last_mult[i+1])
        return result
# 更新，优化
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        pre_mult = [0] * len(nums)
        last_mult = [0] * len(nums)
        pre_mult[0] = 1
        for i in range(1, len(nums)):
            pre_mult[i] = nums[i-1] * pre_mult[i-1]
        last_mult[len(nums) - 1] = 1
        for i in range(len(nums)-2, -1, -1):
            last_mult[i] = nums[i+1] * last_mult[i+1]
        result = [0] * len(nums)
        for i in range(len(nums)):
            result[i] = pre_mult[i] * last_mult[i]
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

时间复杂度：O(n)
空间复杂度：O(n)

解题思路二：优化空间，在维护前后缀数组的同时，更新答案。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        result[0] = 1
        for i in range(1, n):
            result[i] = nums[i-1] * result[i-1]
        R = 1
        for i in range(n-1, -1, -1):
            result[i] = result[i] * R
            R *= nums[i]
        return result
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)
空间复杂度：O(1)

解题思路三：0

1

时间复杂度：O(n)
空间复杂度：O(n)