Skip to main content

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

解题方法​

方法一​

  • 思路：使用两个并列 for 循环，一个 for 循环拿到数组当前索引之前的所有数的积，另一个循环拿到数组当前索引之后的所有数的积，最后将两个循环后的值相乘即可得到答案
  • 复杂度分析：
    • 时间复杂度：O(n)
    • 空间复杂度: O(1)
var productExceptSelf = function (nums) {
  let res = [];
  res[0] = 1;

  for (let i = 1; i < nums.length; i += 1) {
    res[i] = res[i - 1] * nums[i - 1];
  }

  let right = 1;

  for (let i = nums.length - 1; i >= 0; i--) {
    res[i] *= right;
    right *= nums[i];
  }

  return res;
};