除自身以外数组的乘积
除自身以外数组的乘积
给你一个整数数组 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 位 整数范围内
题解：
思路主要是，当前节点的除了自身以外的数的乘积，可以理解为当前节点左边所有数和右边所有数字的乘积，这样呢有点像 leetcode 接雨水的问题，我们可以同时用两个数组来存储左边所有数字的乘积和右边所有数字的乘积，这样对应节点的乘积就是答案；当然了，如果我们想进一步优化空间复杂度，可以使用两个指针，一边移动一遍乘积（方法二）
class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] left = new int[n];int[] right = new int[n];left[0] = 1;for (int i = 1; i < n; i++) {left[i] = nums[i - 1] * left[i - 1];}right[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {right[i] = nums[i + 1] * right[i + 1];}int[] ans = new int[n];for (int i = 0; i < n; i++) {ans[i] = left[i] * right[i];}return ans;}
}
func productExceptSelf(nums []int) (ans []int) {n := len(nums)ans = make([]int, n)lp, rp := 1, 1for i := range ans {ans[i] = 1}for l,r := 0,n-1; l < n && r >=0; l, r = l+1, r-1 {ans[l] *= lpans[r] *= rplp *= nums[l]rp *= nums[r] }return
}