算法题-24

给你一个整数数组 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]

如果直接计算：对于每个位置都遍历一次数组：O(n²)不符合要求。
关键观察，对于某个位置 i：结果 = 左边所有数乘积 × 右边所有数乘积
例如：nums = [1,2,3,4]，求 answer[2]= (1×2) × (4)，因此可以拆成：前缀乘积（left），后缀乘积（right）如果直接计算：对于每个位置都遍历一次数组：O(n²)，不符合要求。
关键观察，对于某个位置 i：结果 = 左边所有数乘积 × 右边所有数乘积
例如：nums = [1,2,3,4]求 answer[2]= (1×2) × (4)

因此可以拆成：前缀乘积（left），后缀乘积（right）

计算左乘积

计算右乘积，right = [24,12,4,1]

var productExceptSelf = function(nums) { const n = nums.length; const left = new Array(n); const right = new Array(n); const ans = new Array(n); left[0] = 1; for (let i = 1; i < n; i++) { left[i] = left[i - 1] * nums[i - 1]; } right[n - 1] = 1; for (let i = n - 2; i >= 0; i--) { right[i] = right[i + 1] * nums[i + 1]; } for (let i = 0; i < n; i++) { ans[i] = left[i] * right[i]; } return ans; };

我们发现：left 数组其实可以直接存进 answer 里！因为：answer[i] 最终一定要包含 left[i]，所以：answer 先当 left 用。我们可以把其空间复杂度变为O(1)，但是我们的右乘积要想办法存进去。

我们用：一个变量 right来边走边算右乘积。
为什么可行？右乘积是：i 右边所有数的乘积，如果从右往左走：right *= nums[i]，就能不断累计。
初始化let right = 1（最后一个右边为空）
从右往左遍历

for(let i = n - 1; i >= 0; i--){ answer[i] = answer[i] * right right *= nums[i] }

var productExceptSelf = function(nums) { const n = nums.length const answer = new Array(n) // ① 左乘积 answer[0] = 1 for(let i = 1; i < n; i++){ answer[i] = answer[i - 1] * nums[i - 1] } // ② 右乘积（滚动变量） let right = 1 for(let i = n - 1; i >= 0; i--){ answer[i] *= right right *= nums[i] } return answer };

先用 answer 存前缀积，再用一个变量滚动计算后缀积并乘进去，从而避免额外数组。