除自身以外数组的乘积

更新: 7/4/2026 字数: 0 字 时长: 0 分钟

题目描述

给你一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

约束：

• 题目保证 answer 数组中每个元素都在 32 位整数范围内。
• 请不要使用除法，且要求在 O(n) 时间复杂度内完成。

示例：

输入：nums = [2, 3, 4, 5]
输出：[60, 40, 30, 24]
解释：
  answer[0] = 3×4×5 = 60
  answer[1] = 2×4×5 = 40
  answer[2] = 2×3×5 = 30
  answer[3] = 2×3×4 = 24

思路拆解

出发点：为什么不能直接用除法？

最直觉的做法是：先算出所有元素的总乘积 total，再对每个位置做 answer[i] = total / nums[i]。这确实是 O(n)，但题目明确禁止除法，而且一旦数组里有 0，除法会直接出错（除以 0，或者无法还原）。所以我们要换一条不依赖除法的路。

点击展开暴力解法（O(n²)，仅作对比）

对每个位置 i，重新遍历一遍数组，把除它以外的所有数乘起来。思路直白但时间是平方级，数据一大就超时。

function productExceptSelf(nums) {
  const n = nums.length
  const answer = new Array(n).fill(1)
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (j !== i) answer[i] *= nums[j]  // 跳过自己
    }
  }
  return answer
}

同时提一句「总乘积 ÷ 自身」的除法解法：虽然是 O(n)，但被题目禁止，且遇到 0 会失效，因此不能采用。

关键观察：拆成「左边乘积 × 右边乘积」

对任意位置 i，除它以外的乘积可以天然拆成两半：

这样就完全绕开了除法：每个位置的答案 = 它左边所有数的乘积 × 它右边所有数的乘积。 左右两部分都可以用一遍线性扫描递推出来。

核心思路

用两趟扫描：

1. 第一趟（从左往右）：让 answer[i] 先存下「i 左侧所有元素的乘积」（前缀积）。
2. 第二趟（从右往左）：维护一个变量 suffix 表示「i 右侧所有元素的乘积」，把它乘进 answer[i]。

两趟都只用一个滚动变量，输出数组本身充当存储，因此不需要额外的前缀/后缀数组，额外空间是 O(1)。

一步步看下面的动画

下面的动画用样例 nums = [2, 3, 4, 5] 完整演示两趟扫描：蓝色是第一趟前缀积（左→右），橙色是第二趟后缀积（右→左），绿色为最终答案。可以单步、自动播放或重置。

除自身以外数组的乘积 · 前缀积 × 后缀积演示

样例：nums = [2, 3, 4, 5]，不使用除法，两趟线性扫描

当前阶段：准备

原数组 nums

2[0]

3[1]

4[2]

5[3]

—

结果数组 answer

·[0]

·[1]

·[2]

·[3]

前缀积扫描（左→右）后缀积扫描（右→左）完成

目标：answer[i] = 除 nums[i] 以外所有元素的乘积。不用除法，只做两趟线性扫描：先算每一位「左侧的前缀积」，再乘上「右侧的后缀积」。

步骤 0 / 19

完整代码

/**
 * 除自身以外数组的乘积：不使用除法，O(n) 时间、O(1) 额外空间。
 */
function productExceptSelf(nums) {
  const n = nums.length
  const answer = new Array(n).fill(1)

  // 第一趟：从左往右，answer[i] 先存「i 左侧所有元素的乘积」（前缀积）
  let prefix = 1
  for (let i = 0; i < n; i++) {
    answer[i] = prefix   // 此刻 prefix 正好是 i 左边的乘积
    prefix *= nums[i]    // 累乘当前元素，供右边的位置使用
  }

  // 第二趟：从右往左，把「i 右侧所有元素的乘积」（后缀积）乘进 answer[i]
  let suffix = 1
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix  // 左侧乘积 × 右侧乘积 = 最终答案
    suffix *= nums[i]    // 累乘当前元素，供左边的位置使用
  }

  return answer
}

// 示例
console.log(productExceptSelf([2, 3, 4, 5])) // [60, 40, 30, 24]

易错点

• answer[i] = prefix 必须先赋值再累乘（prefix *= nums[i] 放在赋值之后），否则会把自己也乘进去。
• 两个初始值都为 1：最左边没有元素、最右边也没有元素，空乘积约定为 1。
• 第二趟是 answer[i] *= suffix（乘等号），不是覆盖赋值，否则会丢掉第一趟算好的前缀积。

复杂度分析

解法	时间复杂度	额外空间复杂度	是否使用除法
暴力双重循环			否
总乘积 ÷ 自身			❌ 被禁止
前缀数组 + 后缀数组			否
前缀积 × 后缀积（滚动变量）			否 ✅

注：输出数组 answer 是题目要求的返回结果，按惯例不计入额外空间，因此本解法额外空间为 O(1)。

边界与易错点

• 数组含有 0： 本解法完全不受影响——正因为不用除法，0 只是一个普通乘数。例如 nums = [1, 0] → answer = [0, 1]；有两个及以上 0 时，所有位置都会是 0，也自动正确。
• 单个元素： 若 nums = [x]，则 answer = [1]（除自己以外没有元素，空乘积为 1）。
• 负数： 负号会自然参与乘法，无需特殊处理，符号会正确翻转。
• 溢出： 题目保证结果落在 32 位整数范围内；在 JS 中数值以双精度浮点表示，注意题目给定范围即可，跨语言实现时需留意整数溢出。
• 不要为了「省一趟」而破坏正确性： 前缀、后缀分别是两趟独立扫描，方向相反，prefix/suffix 各自维护，不能混用同一变量。