238. 除自身以外数组的乘积

题目链接（中等）

题目描述

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

题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

数据范围：

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在 32 位整数范围内

进阶：你可以在 $O(1)$ 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

示例

示例 1：

输入： nums = [1,2,3,4]
输出： [24,12,8,6]

示例 2：

输入： nums = [-1,1,0,-3,3]
输出： [0,0,9,0,0]

核心思路

朴素做法：先算出所有数的总乘积，再用总乘积除以 nums[i] 得到答案。

但题目禁止使用除法，而且如果数组里有 0，除法也行不通（除以 0 无意义）。

关键观察：answer[i] 等于「i 左侧所有数的乘积」乘上「i 右侧所有数的乘积」。

$$answer[i] = \left(\prod_{j<i} nums[j]\right) \times \left(\prod_{j>i} nums[j]\right)$$

因此只需分别求出前缀积和后缀积，再相乘即可。

• 方法一：显式构造前缀积数组 L 和后缀积数组 R，最后 L[i] * R[i]；
• 方法二：复用输出数组 answer 存前缀积，再用一个变量滚动算后缀积，空间降到 $O(1)$。

---

方法一：左右乘积数组

思路及解法

用两个数组：

• L[i]：下标 i 左侧所有数的乘积；
• R[i]：下标 i 右侧所有数的乘积。

边界处理：

• L[0] = 1：第一个元素左侧没有数，乘积为 1（乘法单位元）；
• R[n-1] = 1：最后一个元素右侧没有数，乘积为 1。

构造方式：

• 正向遍历：L[i] = L[i-1] * nums[i-1]（在 L[i-1] 基础上再乘上 nums[i-1]）；
• 反向遍历：R[i] = R[i+1] * nums[i+1]。

最后：answer[i] = L[i] * R[i]。

代码

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        L = [0] * n
        R = [0] * n
        answer = [0] * n

        # L[i] = i 左侧所有元素的乘积
        L[0] = 1
        for i in range(1, n):
            L[i] = L[i - 1] * nums[i - 1]

        # R[i] = i 右侧所有元素的乘积
        R[n - 1] = 1
        for i in range(n - 2, -1, -1):
            R[i] = R[i + 1] * nums[i + 1]

        # 左侧乘积 × 右侧乘积
        for i in range(n):
            answer[i] = L[i] * R[i]

        return answer

复杂度分析

• 时间复杂度：$O(n)$，三次线性遍历。
• 空间复杂度：$O(n)$，L、R 两个辅助数组各 $O(n)$（answer 不计入）。

---

方法二：复用输出数组（$O(1)$ 额外空间）✅ 推荐

思路及解法

方法一用了两个额外数组，其实可以省掉：

第一步：把 answer 当成 L 数组，正向遍历一次，存下「每个位置左侧的乘积」：

answer[0] = 1
for i in range(1, n):
    answer[i] = answer[i - 1] * nums[i - 1]

第二步：用一个变量 R 滚动保存「当前位置右侧所有数的乘积」，反向遍历：

• 初始 R = 1（最右侧没有元素）；
• 每步先 answer[i] *= R，得到最终答案；
• 再更新 R *= nums[i]，让 R 扩展到包含 nums[i]（因为它成为下一个位置的右侧元素）。

R = 1
for i in range(n - 1, -1, -1):
    answer[i] = answer[i] * R
    R *= nums[i]

图解（以 nums = [1,2,3,4] 为例）：

i	answer[i]（第一步后）	R（更新前）	answer[i] * R（结果）	R（更新后）
3	6（1×2×3）	1	6	4
2	2（1×2）	4	8	12
1	1（1）	12	12	24
0	1	24	24	24

最终结果 [24,12,8,6]，正确。

代码

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        answer = [0] * n

        # 第一步：answer[i] 表示 i 左侧所有元素的乘积
        answer[0] = 1
        for i in range(1, n):
            answer[i] = answer[i - 1] * nums[i - 1]

        # 第二步：用 R 滚动记录右侧乘积，边算边乘
        R = 1
        for i in range(n - 1, -1, -1):
            answer[i] = answer[i] * R
            R *= nums[i]

        return answer

复杂度分析

• 时间复杂度：$O(n)$，两次线性遍历。
• 空间复杂度：$O(1)$，只用了一个变量 R（输出数组不计入）。

---

两种方法对比

方法	时间	空间（额外）	特点
左右乘积数组	$O(n)$	$O(n)$	思路最直观，容易讲
复用输出数组	$O(n)$	$O(1)$	满足进阶要求，面试首选

推荐：

• 面试：先用方法一讲清「前缀积 × 后缀积」的思路，再优化到方法二，展示空间优化意识；
• 直接写代码：方法二，空间最优且代码不长。

---

关键细节

1. 为什么用 1 作边界值

L[0] = 1 和 R[n-1] = 1 是乘法的单位元。因为第一个元素左侧没有数、最后一个元素右侧没有数，用 1 可以让公式 answer[i] = L[i] * R[i] 统一成立，不需要特判边界。

2. 为什么不能用除法

• 题目明确禁止使用除法；
• 即使允许，若 nums 里有 0，除以 0 也会出错。

所以必须走「前缀积 × 后缀积」的路线。

3. 方法二第二步的顺序

for i in range(n - 1, -1, -1):
    answer[i] = answer[i] * R    # 先用当前 R 算出 answer[i]
    R *= nums[i]                  # 再把 nums[i] 加进 R

顺序不能反。如果先 R *= nums[i]，那么 R 就包含了 nums[i]，此时 answer[i] * R 会把 nums[i] 也算进去，结果错误。

4. 输出数组不计入空间复杂度

题目明确说明「出于对空间复杂度分析的目的，输出数组不被视为额外空间」。所以方法二用 answer 存前缀积不违反 $O(1)$ 空间的要求。

5. 与「前缀和」的类比

• 前缀和：prefix[i] = prefix[i-1] + nums[i-1]，用于「求区间和」；
• 前缀积：prefix[i] = prefix[i-1] * nums[i-1]，用于「求区间积」。

本题用的就是前缀积 + 后缀积的组合。

---

总结

• 核心等式：answer[i] = 左侧所有数之积 × 右侧所有数之积；
• 方法一：显式构造 L、R 两个数组，最后相乘，空间 $O(n)$；
• 方法二：把 answer 当 L 数组，反向遍历时用变量 R 滚动后缀积，空间 $O(1)$；
• 易错点：
  • 边界值必须取 1，不能取 0；
  • 方法二第二步要先算 answer[i] 再更新 R，顺序不能反；
• 通用套路：「除自身以外」这类问题，通常都可以用「前缀 + 后缀」的组合拆解。

相关题目

• LC 152. 乘积最大子数组（乘法 + DP）
• LC 42. 接雨水（前后缀最大值）
• LC 135. 分发糖果（左右各扫一遍）
• LC 剑指 Offer 66. 构建乘积数组（本题原题）