LeetCode-238.除了自身以外数组的乘积

数组#

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

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

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

示例 1:

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

示例 2:

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

看了思路后写的

思路：就像题目说的一样，用前缀和和后缀和，不过这里是积

1
func productExceptSelf(nums []int) []int {
2
    n := len(nums)
3
    res := make([]int,n)
4
    left := make([]int,n)
5
    right := make([]int,n)
6

7
    left[0] = 1
8
    for i := 1; i < n; i++ {
9
        left[i] = left[i-1] * nums[i-1]
10
    }
11

12
    right[n-1] = 1
13
    for i := n-2; i >= 0; i-- {
14
        right[i] = right[i+1] * nums[i+1]
15
    }
16

17
    for i := 0; i < n; i++ {
18
        res[i] = left[i]*right[i]
19
    }
20

21
    return res
22
}

更优化的方法

1
func productExceptSelf(nums []int) []int {
2
    n := len(nums)
3
    ans := make([]int, n)
4

5
    ans[0] = 1
6
    for i := 1; i < n; i++ {
7
        ans[i] = ans[i-1] * nums[i-1]
8
    }
9

10
    rightProduct := 1
11
    for i := n - 1; i >= 0; i-- {
12
        ans[i] = ans[i] * rightProduct
13
        rightProduct *= nums[i]
14
    }
15

16
    return ans
17
}