企业官网建设流程全解析

LeetCode-Book 剑指 Offer 66：构建乘积数组——不用除法的 O(N) 上三角/下三角分解详解

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本篇围绕 剑指 Offer 66. 构建乘积数组 这一经典笔试题展开：如何在不使用除法的约束下，仅用乘法构造“除自身外数组乘积”。文中完整继承原图文的核心思路、算法流程与三语言代码，并结合 LeetCode-Book 仓库中 Python、Java、C++ 三份可运行的解题代码逐行解析，最终给出时间 O(N)、额外空间 O(1) 的标准解法，以及一个完整的算例推演过程。

1. 题目描述与约束

给定一个数组a，构造数组b，其中b[i]是数组a中除了a[i]以外其余所有元素的乘积。题目禁止使用除法，例如输入[1, 2, 3, 4, 5]时，期望输出[120, 60, 40, 30, 24]。

这道题是面试中“禁用某类运算”型题目的高频代表。暴力解法对每个i都遍历一次数组求乘积，时间复杂度为 O(N²)；若允许除法，则可先求全局乘积再除回a[i]，得到 O(N) 解法——但除法被明确禁止（且它还会在a[i] = 0时触发除零错误）。本题的难点正在于：只用乘法，也能达到 O(N)。

2. 核心思路：乘积矩阵的上三角/下三角分解

按b[i]的定义，把所有参与b[i]计算的元素排成一张 N×N 表格（b[i]对应第i行、a[j]对应第j列，j == i处因不参与乘积记为 1）：

a[0] a[1] a[2] a[3] a[4] b[0] 1 2 3 4 5 b[1] 1 1 3 4 5 b[2] 1 2 1 4 5 b[3] 1 2 3 1 5 b[4] 1 2 3 4 1

可以发现两个关键性质：

• 主对角线全为 1（乘法单位元），即被排除的元素自己；
• 表格被主对角线干净地划分为上三角与下三角两块，且每一块内部的元素都具有“按行前缀/后缀递推”的规律。

于是可以分两轮迭代，每轮只累乘相邻关系中的增量部分，而无需重复计算：

1. 下三角（正向遍历）：b[i]的下三角部分是a[0] × a[1] × … × a[i-1]，它是前一个下三角乘积b[i-1]乘以a[i-1]即可得到的前缀积。直接把这个值写进b[i]；
2. 上三角（反向遍历）：b[i]的上三角部分是a[i+1] × … × a[N-1]，它同样可由后一个上三角乘积逐步左移累乘得到。用一个辅助变量tmp沿右到左滚动累乘，每步将tmp乘回b[i]；
3. 两轮之后，b[i] = 下三角乘积 × 上三角乘积，恰好是除a[i]外全部元素的乘积，全程只用了乘法。

3. 算法流程（继承原图文四步法）

1. 初始化：数组b全部置 1（b[0] = 1）；辅助变量tmp = 1；
2. 计算下三角：正向遍历，b[i] = b[i-1] * a[i-1]，把b[i]的下三角各元素乘积直接乘入b[i]；
3. 计算上三角：反向遍历，tmp *= a[i+1]，再b[i] *= tmp，即“下三角 × 上三角”；
4. 返回b。

3.1 算例推演：a = [1, 2, 3, 4, 5]

这是仓库三份代码中统一采用的测试用例（见 Python 代码第 23 行）。

第一轮（下三角，i 从 1 到 4）：

第二轮（上三角，i 从 3 倒到 0，tmp 初值 1）：

最终b = [120, 60, 40, 30, 24]，与期望输出一致。

4. 三语言解题代码（仓库源码逐行解析）

以下代码均取自 LeetCode-Book 仓库sword_for_offer/codes目录，文件头部带有创建时间与作者信息，并内置测试用例驱动，可直接编译运行。

4.1 Python

来自 sfo_66_a_product_array_puzzle_s1.py：

class Solution: def constructArr(self, a: List[int]) -> List[int]: b, tmp = [1] * len(a), 1 for i in range(1, len(a)): b[i] = b[i - 1] * a[i - 1] # 下三角 for i in range(len(a) - 2, -1, -1): tmp *= a[i + 1] # 上三角 b[i] *= tmp # 下三角 * 上三角 return b

要点：

• [1] * len(a)一行完成整个b数组的全 1 初始化，b[0] = 1天然成立；
• 当输入为空数组时，range(1, 0)与range(-2, -1, -1)均为空迭代，函数直接返回[]，因此Python 版本无需显式判空，这一点比 Java/C++ 版本更简洁；
• 反向遍历用range(len(a) - 2, -1, -1)，从N-2一直走到0。

4.2 Java

来自 sfo_66_a_product_array_puzzle_s1.java：

public int[] constructArr(int[] a) { int len = a.length; if (len == 0) return new int[0]; // 显式处理空数组 int[] b = new int[len]; b[0] = 1; // 注意 Java int[] 默认值是 0，必须先手动置 1 int tmp = 1; for (int i = 1; i < len; i++) { b[i] = b[i - 1] * a[i - 1]; // 下三角 } for (int i = len - 2; i >= 0; i--) { tmp *= a[i + 1]; // 上三角 b[i] *= tmp; // 下三角 * 上三角 } return b; }

要点：Java 中int[]元素默认初始化为0，而本算法要求b初始全为 1（因为 0 会把前缀积清零），所以b[0] = 1加上循环里的赋值b[i] = b[i-1] * a[i-1]必须配合完整——第一轮循环结束后每个b[i]都会被覆盖为前缀积，不存在遗漏。

4.3 C++

来自 sfo_66_a_product_array_puzzle_s1.cpp：

vector<int> constructArr(vector<int>& a) { int len = a.size(); if (len == 0) return {}; vector<int> b(len, 1); // 构造时整体初始化为 1 b[0] = 1; int tmp = 1; for (int i = 1; i < len; i++) { b[i] = b[i - 1] * a[i - 1]; } for (int i = len - 2; i >= 0; i--) { tmp *= a[i + 1]; b[i] *= tmp; } return b; }

要点：vector<int> b(len, 1)利用构造函数一次性把len个元素全部填 1，等价于 Python 的[1] * len(a)，这是 C++ 版本最不易出错的初始化方式。

4.4 三语言实现差异小结

三个版本在 测试用例 上保持一致：输入{1, 2, 3, 4, 5}，输出[120, 60, 40, 30, 24]，可直接作为自检基准。

5. 复杂度分析

• 时间复杂度 O(N)：其中 N 为数组长度。算法只做两轮线性遍历（下三角一轮、上三角一轮），每轮每次循环仅做常数次乘法，共 O(N) 时间。相比暴力 O(N²) 与“先求总积再除”的思路，既满足禁用除法的约束，又达到了线性复杂度下界；
• 空间复杂度 O(1)：除返回数组b之外，只使用了变量tmp一个常量额外空间（返回数组不计入复杂度考虑）。

6. 关联题：同构算法在 LeetCode 238 中的复用

本仓库的“Krahets 笔面试精选 88 题”部分收录了算法骨架完全相同的 238. 除自身以外数组的乘积：输入nums、输出ans，同样禁用除法。其解法 lc_238_product_of_array_except_self.py 与剑指 Offer 66 的差异仅在函数名（productExceptSelfvsconstructArr）与变量名（ansvsb），上三角/下三角两轮累乘的结构逐行一致。掌握本题后，这两道高频面试题可以视为同一模板的两副面孔，建议对照复习。

7. 小结

• “禁止除法”约束下的最优解，是把每个b[i]的乘积分解为下三角前缀积与上三角后缀积两部分，分别用正向、反向各一轮线性扫描滚动累乘得到；
• 实现上的三个易错点：结果数组必须初始化为全 1 而非全 0；反向轮次中tmp要先乘a[i+1]再乘回b[i]，顺序不可颠倒；Java/C++ 需显式处理空数组而 Python 无需；
• 完整题解文档见 剑指 Offer 66. 构建乘积数组，三语言可运行代码位于 sword_for_offer/codes 目录，该题在 剑指 Offer 刷题计划 中也已列入规划，可作为笔面试动态规划/数组技巧专题的收尾题练习。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book