238. 除自身以外数组的乘积 (Medium)
专题归类： 数组 · 前缀和 LeetCode 链接： https://leetcode.cn/problems/product-of-array-except-self/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
要求： 不能使用除法，且必须在 O(n) 时间内完成。
示例 1：
输入：nums = [1,2,3,4]
输出：[24,12,8,6]
解释：
answer[0] = 2×3×4 = 24
answer[1] = 1×3×4 = 12
answer[2] = 1×2×4 = 8
answer[3] = 1×2×3 = 6
示例 2：
输入：nums = [-1,1,0,-3,3]
输出：[0,0,9,0,0]
补充说明：
2 <= nums.length <= 10^5-30 <= nums[i] <= 30- 题目数据保证所有元素乘积在 32 位整数范围内
- 进阶：能否在 O(1) 额外空间内完成？（输出数组不计入空间复杂度）
题目详细分析
数据范围分析：
- 数组长度最大 10^5，暴力算法（对每个位置算其他所有元素的乘积）O(n^2) 不可行。
- 元素值范围 -30~30，乘积不会太大（保证在 32 位内）。
- 数组中可能包含 0，这是除法方案失效的关键原因。
输入输出特征：
- 输入是整数数组，输出是与输入等长的整数数组。
answer[i]不包含nums[i]本身，等于其他所有元素的乘积。
边界条件：
- 数组包含一个 0：0 所在位置的结果是其他元素的乘积（非零），其他位置结果是 0。
- 数组包含多个 0：所有位置的结果都是 0。
- 数组长度为 2：这是最小长度，
answer[0] = nums[1],answer[1] = nums[0]。 - 数组包含负数：正常相乘即可，负负得正。
隐藏条件：
- 禁止使用除法是本题的核心约束。如果允许除法，可以算总乘积再除以每个元素，但 0 的存在使除法不可行。
- O(1) 额外空间的进阶要求意味着不能使用两个额外数组分别存储前缀积和后缀积。
小白版直白理解
假如你和 3 个朋友一起做小组作业，老师要给你们每个人打分，但规则很特别：
你的分数 = 其他 3 个同学分数的乘积。
也就是说：
- 同学 A 的分数 = B × C × D
- 同学 B 的分数 = A × C × D
- 同学 C 的分数 = A × B × D
- 同学 D 的分数 = A × B × C
笨办法： 每次算一个人的分数，都把其他人的分数乘一遍。4 个人还好，要是有 10 万人就太慢了。
聪明法：
- 从左到右走一遍，记下”到当前位置之前所有人的乘积”——这就是前缀积。
- 从右到左再走一遍，记下”从当前位置之后所有人的乘积”——这就是后缀积。
- 对每个人，前缀积 × 后缀积 = 最终分数。
只用了两趟扫描，而且不需要额外的数组来记（直接写在结果数组里）。
生活类比： 就像做接力赛，先从左到右传棒（前缀积），再从右到左传棒（后缀积），每个人拿到两个方向的接力棒就完成任务了。
解题思路
思路一：前缀积 + 后缀积，O(1) 额外空间（推荐）
核心洞察：
answer[i] 可以拆解为两部分：nums[0..i-1] 的乘积 × nums[i+1..n-1] 的乘积。
用两次遍历：
- 从左到右：用
left_prod累乘，把每个位置左边的乘积存入结果数组 - 从右到左：用
right_prod累乘，乘到结果数组的对应位置上
这样结果数组直接用上了，不需要额外的左右乘积数组。
def productExceptSelf(nums):
n = len(nums)
res = [1] * n
# 第一次遍历：左边乘积
# res[i] = nums[0] * nums[1] * ... * nums[i-1]
left_prod = 1
for i in range(n):
res[i] = left_prod
left_prod *= nums[i]
# 第二次遍历：右边乘积
# 将右边乘积乘到 res[i] 上
right_prod = 1
for i in range(n - 1, -1, -1):
res[i] *= right_prod
right_prod *= nums[i]
return res复杂度： O(n) 时间，O(1) 额外空间（输出数组不算）。
思路二：左右乘积数组（更易理解，但空间 O(n)）
用两个额外数组分别存储每个位置左边和右边的乘积，最后合到一起。这种方式更直观，但不满足 O(1) 额外空间的要求。
def productExceptSelf_extraSpace(nums):
n = len(nums)
left = [1] * n
right = [1] * n
# 左边乘积
for i in range(1, n):
left[i] = left[i - 1] * nums[i - 1]
# 右边乘积
for i in range(n - 2, -1, -1):
right[i] = right[i + 1] * nums[i + 1]
# 合成结果
res = [left[i] * right[i] for i in range(n)]
return res思路三：用除法（不可取但可以思考对比）
先计算所有元素的乘积 total，然后 answer[i] = total // nums[i]。
问题在于：
- 如果有 0，除法会出问题（多个 0 / 单个 0）
- 题目明确禁止使用除法
- 如果元素值很大，
total可能溢出
def productExceptSelf_div(nums):
total = 1
zero_count = nums.count(0)
if zero_count >= 2:
return [0] * len(nums)
for num in nums:
if num != 0:
total *= num
res = []
for num in nums:
if zero_count == 1:
res.append(total if num == 0 else 0)
else:
res.append(total // num)
return res易错点
- 初始化顺序：在第一次遍历中，先赋值
res[i] = left_prod，再更新left_prod *= nums[i]。如果搞反顺序，res[i]会包含nums[i]本身。 - 第二次遍历方向：必须从右向左遍历，否则后缀积无法正确累乘。
- 结果数组初始值：初始化为
[1] * n，因为乘积的初始值是 1 而不是 0。 - 包含 0 的情况：如果有 0，除法方案失效，但前缀积+后缀积不受影响。
- 空数组/单元素数组：题目说长度至少为 2，所以不用处理。
- 乘积顺序理解：
res[i]是除了 nums[i] 之外的乘积，不要搞反。
框架提炼
前缀/后缀积通用模板（数组原地操作）：
def array_except_self(nums):
n = len(nums)
res = [1] * n # 初始值：乘法单位元
# Step 1: 从左到右 —— 前缀累乘
prefix = 1
for i in range(n):
res[i] = prefix # 先赋值（不含当前元素的前缀值）
prefix *= nums[i] # 再更新（包含当前元素）
# Step 2: 从右到左 —— 后缀累乘
suffix = 1
for i in range(n - 1, -1, -1):
res[i] *= suffix # 乘上后缀值
suffix *= nums[i] # 更新后缀
return res模式总结： 这个「两遍扫描」的模式广泛用于需要同时利用左边信息和右边信息的问题：
核心公式：
answer[i] = f(nums[0..i-1]) ∘ g(nums[i+1..n-1])
其中 f 和 g 是某种可累积运算（和、积、最大值等），∘ 是组合运算。
关联题目
- 42-接雨水 — 使用类似的两遍扫描思想：每个位置能接的雨水 = min(左边最高柱子, 右边最高柱子) - 当前高度。
- 135-分发糖果 — 两次遍历：先从左到右保证右边比左边评分高则多拿糖果，再从右到左保证左边比右边评分高则多拿糖果。
- 189-轮转数组 — 同样是数组原地操作的问题，使用的是三次翻转法而非前缀/后缀思想。
- 152-乘积最大子数组 — 同样是乘积相关的问题，但要求的是连续子数组的最大乘积，使用的是 Kadane 算法变体。