LeetCode 剑指 Offer 66. 构建乘积数组
目录
题目描述
题意分析
给定数组
a，要构造等长的数组b，使b[i]等于a中除了a[i]之外所有元素的乘积。题目明确禁止使用除法，这是全题最重要的一句话。没有这条限制，先算总乘积再逐位相除是两行代码的事；加上这条限制，就必须换一种把「排除自己」表达出来的方式。
禁用除法并不只是为了增加难度。数组里可能有 $0$，总乘积会变成 $0$，除法在 $0$ 的位置无法定义，还要额外分「有一个零」「有多个零」「没有零」三种情况讨论。规避除法的做法能让这三种情况自动统一。
数据规模上要求线性时间，所以逐个位置去乘一遍其它元素的平方级做法不可行。空间上通常还会追问能否做到除输出数组外只用常数额外空间。
边界要提前想清楚：数组为空时返回空数组；只有一个元素时，除它以外没有任何元素，乘积按空积约定为 $1$；元素可能为负，符号要靠乘法自然传递而不能另外处理。
解法：前后缀乘积
核心思路
朴素做法是对每个下标 i 再扫一遍整个数组，把除
a[i]之外的元素连乘起来，代价是 $O(n^2)$。瓶颈在于相邻两个位置的答案其实高度重叠，却被完全独立地重算了一遍。把「除自己以外的乘积」拆开看：它等于「下标严格小于 i 的所有元素之积」乘上「下标严格大于 i 的所有元素之积」。这两个量分别是前缀积和后缀积，它们各自都能在一次线性扫描里递推出来。这个拆分不需要任何除法，因为它压根没有先把
a[i]乘进去再拿出来，而是从一开始就绕开了它。这也正是 $0$ 不再是麻烦的原因：某个位置的 $0$ 只会出现在包含它的那些前后缀里，b的对应位置自然就是 $0$，而排除掉这个 $0$ 的那个位置也自然算出非零结果，一行特判都不需要。维持的不变量是：第一趟从左往右扫完之后，
res[i]恰好等于a[0]到a[i - 1]的乘积，也就是 i 左侧的前缀积，其中res[0]是空积 $1$。第二趟从右往左扫，用一个滚动变量right保持「已经走过的、严格在 i 右侧的元素之积」，进入下标 i 时right等于a[i + 1]到a[n - 1]的乘积。两趟合起来，在第二趟处理下标 i 时把
res[i]乘上right，得到的就是左侧积乘右侧积，正是答案。之所以能省掉后缀数组，是因为第二趟对res[i]的读写恰好发生在right更新之前，两者的先后顺序保证了right里不含a[i]自己。
解题步骤
- 先处理空数组，直接返回空数组。这是唯一一处必须的特判，因为后面要写
res[0]，长度为零时没有这个位置可写。- 创建与输入等长的结果数组
res，并令res[0] = 1。这个 $1$ 不是随便挑的初值，它表示下标 $0$ 左边没有元素时的空积，是整条前缀递推的锚点。- 从 i = 1 递增到 n - 1，令
res[i] = res[i - 1] * a[i - 1]。注意乘的是a[i - 1]而不是a[i]：res[i - 1]已经是 i - 1 左侧的积，再补上a[i - 1]本身，才凑成 i 左侧的积，这样a[i]始终没被乘进去。- 初始化滚动变量
right = 1，代表最右端右侧没有元素时的空积。- 从 i = n - 1 递减到 $0$，每轮先执行
res[i] = res[i] * right，再执行right = right * a[i]。这两句的顺序不能交换：先乘是为了让right此刻只包含 i 右侧的元素；后更新是为了让right在进入下一个（更左的）下标时把a[i]纳入进来。- 返回
res。左侧积在第一趟已写入，右侧积在第二趟原地乘上，全程没有第二个数组。以
a = [1, 2, 3, 4, 5]走一遍：第一趟先把res[0]置为 $1$。i = 1 时res[1] = res[0] * a[0] = 1 * 1 = 1；i = 2 时res[2] = res[1] * a[1] = 1 * 2 = 2；i = 3 时res[3] = res[2] * a[2] = 2 * 3 = 6；i = 4 时res[4] = res[3] * a[3] = 6 * 4 = 24。此时res = [1, 1, 2, 6, 24]，每一项确实是各自左侧元素的乘积。第二趟令
right = 1。i = 4 时先算res[4] = 24 * 1 = 24，再更新right = 1 * 5 = 5。i = 3 时先算res[3] = 6 * 5 = 30，再更新right = 5 * 4 = 20。i = 2 时先算res[2] = 2 * 20 = 40，再更新right = 20 * 3 = 60。i = 1 时先算res[1] = 1 * 60 = 60，再更新right = 60 * 2 = 120。i = 0 时先算res[0] = 1 * 120 = 120，再更新right = 120 * 1 = 120（此后不再使用）。最终
res = [120, 60, 40, 30, 24]。逐项核对：$2 \times 3 \times 4 \times 5 = 120$，$1 \times 3 \times 4 \times 5 = 60$，$1 \times 2 \times 4 \times 5 = 40$，$1 \times 2 \times 3 \times 5 = 30$，$1 \times 2 \times 3 \times 4 = 24$，全部吻合。
代码实现
class Solution {
// 不能使用除法，因此不能通过总乘积直接相除。
public int[] constructArr(int[] a) {
if (a.length == 0) {
return new int[0];
}
int n = a.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * a[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] = res[i] * right;
right *= a[i];
}
return res;
}
}
func constructArr(a []int) []int {
// 不能使用除法，因此不能通过总乘积直接相除。
if len(a) == 0 {
return []int{}
}
n := len(a)
res := make([]int, n)
res[0] = 1
for i := 1; i < n; i++ {
res[i] = res[i-1] * a[i-1]
}
right := 1
for i := n - 1; i >= 0; i-- {
res[i] = res[i] * right
right *= a[i]
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，其中 n 是数组长度。两趟独立的线性扫描，每个下标各被访问两次，每次只做一到两次乘法和一次赋值，没有嵌套循环也没有回退。
- 空间复杂度：$O(1)$，不计必须返回的结果数组时只用了
right和循环下标这几个变量。关键在于第二趟把后缀积压缩成了一个滚动标量，并直接在res上原地累乘，省掉了通常写法里的那个后缀数组。
关键点总结
- 「排除自己」的量几乎都可以拆成「自己左边的」乘（或加）「自己右边的」。这个拆分把一个看似需要全局信息的量，变成了两个方向上各自可递推的局部量，是前后缀类问题的通用入口。
- 禁用除法不只是形式约束，它同时也消灭了 $0$ 带来的分类讨论。看到「不许用除法」时，要意识到出题人往往正是想让你避开这些特判。
- 前缀递推的初值取空积 $1$，而不是
a[0]。把「什么都不乘」显式表示成单位元，是让边界被主循环吞掉的标准手法，加法版本里对应的就是 $0$。- 第二趟里「先用后更新」的顺序是正确性的全部依托。凡是用滚动变量替代辅助数组，都要能一句话说清这个变量在读取时刻代表什么区间。
- 面试视角：面试官几乎一定会追问空间能否再降。要能主动指出结果数组是题目要求的输出、不计入额外空间，然后把后缀数组换成标量，这一步是本题的得分点。
- 面试视角：另一个常见追问是「如果允许用除法，代码要多写什么」。要能答出至少得分类统计零的个数：零多于一个则全为 $0$，恰好一个则只有那个位置非零，没有零才能直接除，用这段对比反衬前后缀写法的简洁。
易错点总结
- 错误写法：前缀递推写成
res[i] = res[i - 1] * a[i]→ 把a[i]自己也乘了进去，res[i]变成包含自身的前缀积。以a = [1, 2, 3, 4, 5]为例，第一趟得到[1, 2, 6, 24, 120]，最终每一项都多乘了一个a[i]，答案全错。- 错误写法：第二趟把两句顺序写反，先
right *= a[i]再res[i] *= right→right里混进了a[i]自己。以a = [1, 2, 3, 4, 5]为例，i = 4 时right先变成 $5$，res[4]得到 $120$，而正确值是 $24$。- 错误写法：
res[0]初始化为a[0]或 $0$ → 初值为 $0$ 时整条前缀积恒为 $0$，输出全零；初值为a[0]则相当于把自身乘了进去，与第一条同类。空积必须取乘法单位元 $1$。- 错误写法：
right初始化为 $0$ → 第二趟每一项都被乘成 $0$，返回全零数组，而且这个错误在数组本身含 $0$ 时更难被发现。- 错误写法：先算总乘积再逐位相除 → 题目明令禁止；即便强行使用，
a中含 $0$ 时总乘积为 $0$，在零的位置会触发除零异常，含两个以上零时结果更是全错。- 错误写法：为数组中的 $0$ 单独加特判分支 → 前后缀写法里 $0$ 会被乘法自然吸收，额外的特判不仅冗余，还容易在「恰好一个零」和「多个零」的判定上写反，把本来正确的结果改坏。
- 错误写法：省掉长度为零的判断直接写
res[0] = 1→ 空数组时下标越界，而题目允许输入为空。- 错误写法：认为长度为 $1$ 需要特判返回
[0]→ 除掉唯一元素后没有任何元素相乘，按空积约定应返回[1]。主循环本身就能给出这个结果，多写的特判反而制造了错误。- 错误写法：用
int累乘却不考虑量级 → 前后缀积是若干元素的连乘，元素个数一多就可能越过int上界而静默回绕，题目若给出更大的取值范围就必须换成更宽的整型。- 错误写法：第二趟仍然新开一个后缀数组 → 结果正确但额外空间退回 $O(n)$，在面试里会被直接追问「能不能优化」，等于白白丢掉本题最关键的一问。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 238. 除了自身以外数组的乘积 | 中等 | 与本题同题，官方进阶明确要求 $O(1)$ 额外空间，可直接对照优化过程 |
| 724. 寻找数组的中心下标 | 简单 | 把乘法换成加法，用总和减前缀即得后缀，是同一拆分思路的加法版 |
| 303. 区域和检索 - 数组不可变 | 简单 | 前缀和的多次查询形态，考察预处理与查询的代价划分 |
| 42. 接雨水 | 困难 | 前后缀取的是最大值而非乘积，且可进一步用双指针把两趟压成一趟 |
| 152. 乘积最大子数组 | 中等 | 同样是连乘，但要同时维护最大与最小两个状态来应对负数翻转符号 |