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 <= $10^5$
• -30 <= nums[i] <= 30
• 保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内

解析

两趟扫描：先从左到右计算前缀积，再从右到左乘以后缀积。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  const n = nums.length;
  const result = new Array(n);

  // 从左到右：result[i] = 左边所有元素的乘积
  result[0] = 1;
  for (let i = 1; i < n; i++) {
    result[i] = result[i - 1] * nums[i - 1];
  }

  // 从右到左：乘以右边所有元素的乘积
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= right;
    right *= nums[i];
  }

  return result;
};

不使用除法，用前缀积和后缀积的乘积得到除自身外的乘积。时间复杂度 O(n)，空间复杂度 O(1)（结果数组不算额外空间）。