238.除自身以外数组的乘积
238.除自身以外数组的乘积
题解
题目：给定一个数组，求除自身以外数组的乘积，并要求时间复杂度O(n)，空间复杂度O(1)
思路：
1.O(n)的复杂度，说明要遍历两次 2.第一次遍历，累计左边数组的乘积，注意边界lSum[0]=1 3.第二次遍历，累计右边数组的乘积，注意边界rSum[n-1]=1 4.第三次遍历，除自身以外数组的乘积=lSum[i]*rSum[i]
优化
上面的做法，时间复杂度是满足了，但是空间复杂度不满足 1.发现左边数组的乘积，可以直接用返回的数组代替 2.而右边的乘积，我们可以边更新答案，边用一个变量去计算累计乘积 3.这个空间复杂度就O(1)了
代码
func productExceptSelf(nums []int) []int { n := len(nums) lSum, rSum := make([]int, n+1), make([]int, n+1) ans := make([]int, n) lSum[0], rSum[n-1] = 1, 1 for i := 1; i <= n; i++ { lSum[i] = lSum[i-1] * nums[i-1] } for i := n - 2; i >= 0; i-- { rSum[i] = rSum[i+1] * nums[i+1] } for i := 0; i < n; i++ { ans[i] = lSum[i] * rSum[i] } return ans }
func productExceptSelf(nums []int) []int { n := len(nums) ans := make([]int, n) ans[0] = 1 for i := 1; i < n; i++ { ans[i] = ans[i-1] * nums[i-1] } rSum := 1 for i := n - 1; i >= 0; i-- { ans[i] = ans[i] * rSum rSum = rSum * nums[i] } return ans }
