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
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
38
39
40
41
42
43
44
45
46
47
48
49
func productExceptSelf(nums []int) []int { 
	length := len(nums) 
	
	// L 和 R 分别表示左右两侧的乘积列表 
	L, R, answer := make([]int, length), make([]int, length), make([]int, length) 
	// L[i] 为索引 i 左侧所有元素的乘积 
	// 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1 
	L[0] = 1 
	for i := 1; i < length; i++ { 
		L[i] = nums[i-1] * L[i-1] 
	} 
	// R[i] 为索引 i 右侧所有元素的乘积 
	// 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1 
	R[length-1] = 1 
	for i := length - 2; i >= 0; i-- { 
		R[i] = nums[i+1] * R[i+1] 
	} 
	// 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积 
	for i := 0; i < length; i++ { 
		answer[i] = L[i] * R[i] 
	} 
	return answer 
} 


// O(1) 版本
func productExceptSelf(nums []int) []int {
	length := len(nums)
	ans := make([]int, length)
	var x int

	// ans[i] 表示索引 i 左侧所有元素的乘积
    // 因为索引为 '0' 的元素左侧没有元素， 所以 ans[0] = 1
	ans[0] = 1
	for i:=1; i<len(nums); i++ {
		ans[i] = nums[i-1] * ans[i-1]
	}
	
	// x 为右侧所有元素的乘积
	// 刚开始右边没有元素，所以 x = 1
	x = 1
	for j:=length-1; j >=0; j-- {
		// 对于索引 i，左边的乘积为 ans[i]，右边的乘积为 x
		ans[j] = ans[j] * x
		// x 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 x 上
		x = nums[j] * x
	}
	return ans
}