238.M 除自身以外数组的乘积

Problem: 238. 除自身以外数组的乘积

思路

如果可以用除法的话，此题很简单，先计算所有数组的乘积，然后再除以当前位置的数字，即可得到当前位置的结果。

由于不能用除法，考虑用除法，每个位置的结果等于 左侧所有数字的乘积 * 右侧所有数字的乘积 。初始化两个数组，left用于存储左侧数字的乘积，right用于存储右侧数字的乘积。对于位置i来说，结果等于 left[i-1]*right[i+1]

以上解法空间复杂度不是O(1)，为了减少空间，可以用ans数组来充当left数组的功能，然后从右侧开始逐渐计算结果，这样只需要一个数字即可保存右侧n个数字的乘积。

Code

解法一：

func productExceptSelf(nums []int) []int {
	left := make([]int, len(nums))
	left[0] = nums[0]
	right := make([]int, len(nums))
	right[len(nums)-1] = nums[len(nums)-1]
	for i := 1; i < len(nums); i++ {
		left[i] = left[i-1] * nums[i]
	}

	for i := len(nums) - 2; i >= 0; i-- {
		right[i] = right[i+1] * nums[i]
	}

	ans := make([]int, len(nums))
	ans[0] = right[1]
	ans[len(nums)-1] = left[len(nums)-2]
	for i := 1; i < len(nums)-1; i++ {
		ans[i] = left[i-1] * right[i+1]
	}

	return ans
}

解法二：

func productExceptSelf(nums []int) []int {
	ans := make([]int, len(nums))
	ans[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		ans[i] = ans[i-1] * nums[i]
	}

	right := 1
	for i := len(nums) - 1; i > 0; i-- {
		ans[i] = ans[i-1] * right
		right *= nums[i]
	}
	ans[0] = right

	return ans
}
···