 上三角/下三角分解详解)
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处因不参与乘积记为 1a[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乘法单位元即被排除的元素自己表格被主对角线干净地划分为上三角与下三角两块且每一块内部的元素都具有“按行前缀/后缀递推”的规律。于是可以分两轮迭代每轮只累乘相邻关系中的增量部分而无需重复计算下三角正向遍历b[i]的下三角部分是a[0] × a[1] × … × a[i-1]它是前一个下三角乘积b[i-1]乘以a[i-1]即可得到的前缀积。直接把这个值写进b[i]上三角反向遍历b[i]的上三角部分是a[i1] × … × a[N-1]它同样可由后一个上三角乘积逐步左移累乘得到。用一个辅助变量tmp沿右到左滚动累乘每步将tmp乘回b[i]两轮之后b[i] 下三角乘积 × 上三角乘积恰好是除a[i]外全部元素的乘积全程只用了乘法。3. 算法流程继承原图文四步法初始化数组b全部置 1b[0] 1辅助变量tmp 1计算下三角正向遍历b[i] b[i-1] * a[i-1]把b[i]的下三角各元素乘积直接乘入b[i]计算上三角反向遍历tmp * a[i1]再b[i] * tmp即“下三角 × 上三角”返回b。3.1 算例推演a [1, 2, 3, 4, 5]这是仓库三份代码中统一采用的测试用例见 Python 代码第 23 行。第一轮下三角i 从 1 到 4i计算b[i] 结果b 数组状态初始b [1,1,1,1,1]—[1, 1, 1, 1, 1]1b[1] b[0]*a[0] 1*11[1, 1, 1, 1, 1]2b[2] b[1]*a[1] 1*22[1, 1, 2, 1, 1]3b[3] b[2]*a[2] 2*36[1, 1, 2, 6, 1]4b[4] b[3]*a[3] 6*424[1, 1, 2, 6, 24]第二轮上三角i 从 3 倒到 0tmp 初值 1i计算tmpb[i] 结果3tmp * a[4]→ 5b[3] * 556×5 302tmp * a[3]→ 20b[2] * 20202×20 401tmp * a[2]→ 60b[1] * 60601×60 600tmp * a[1]→ 120b[0] * 1201201×120 120最终b [120, 60, 40, 30, 24]与期望输出一致。4. 三语言解题代码仓库源码逐行解析以下代码均取自 LeetCode-Book 仓库sword_for_offer/codes目录文件头部带有创建时间与作者信息并内置测试用例驱动可直接编译运行。4.1 Python来自 sfo_66_a_product_array_puzzle_s1.pyclass 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.javapublic 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.cppvectorint constructArr(vectorint a) { int len a.size(); if (len 0) return {}; vectorint 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; }要点vectorint b(len, 1)利用构造函数一次性把len个元素全部填 1等价于 Python 的[1] * len(a)这是 C 版本最不易出错的初始化方式。4.4 三语言实现差异小结差异点PythonJavaC空数组处理循环天然为空无需判空显式if (len 0)返回空数组显式if (len 0)返回{}b初始化为全 1[1] * len(a)需手动b[0] 1默认值 0vectorint b(len, 1)反向遍历写法range(len(a)-2, -1, -1)for (i len-2; i 0; i--)同 Java三个版本在 测试用例 上保持一致输入{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[i1]再乘回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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 剑指 Offer 66：构建乘积数组——不用除法的 O(N) 上三角/下三角分解详解
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处因不参与乘积记为 1a[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乘法单位元即被排除的元素自己表格被主对角线干净地划分为上三角与下三角两块且每一块内部的元素都具有“按行前缀/后缀递推”的规律。于是可以分两轮迭代每轮只累乘相邻关系中的增量部分而无需重复计算下三角正向遍历b[i]的下三角部分是a[0] × a[1] × … × a[i-1]它是前一个下三角乘积b[i-1]乘以a[i-1]即可得到的前缀积。直接把这个值写进b[i]上三角反向遍历b[i]的上三角部分是a[i1] × … × a[N-1]它同样可由后一个上三角乘积逐步左移累乘得到。用一个辅助变量tmp沿右到左滚动累乘每步将tmp乘回b[i]两轮之后b[i] 下三角乘积 × 上三角乘积恰好是除a[i]外全部元素的乘积全程只用了乘法。3. 算法流程继承原图文四步法初始化数组b全部置 1b[0] 1辅助变量tmp 1计算下三角正向遍历b[i] b[i-1] * a[i-1]把b[i]的下三角各元素乘积直接乘入b[i]计算上三角反向遍历tmp * a[i1]再b[i] * tmp即“下三角 × 上三角”返回b。3.1 算例推演a [1, 2, 3, 4, 5]这是仓库三份代码中统一采用的测试用例见 Python 代码第 23 行。第一轮下三角i 从 1 到 4i计算b[i] 结果b 数组状态初始b [1,1,1,1,1]—[1, 1, 1, 1, 1]1b[1] b[0]*a[0] 1*11[1, 1, 1, 1, 1]2b[2] b[1]*a[1] 1*22[1, 1, 2, 1, 1]3b[3] b[2]*a[2] 2*36[1, 1, 2, 6, 1]4b[4] b[3]*a[3] 6*424[1, 1, 2, 6, 24]第二轮上三角i 从 3 倒到 0tmp 初值 1i计算tmpb[i] 结果3tmp * a[4]→ 5b[3] * 556×5 302tmp * a[3]→ 20b[2] * 20202×20 401tmp * a[2]→ 60b[1] * 60601×60 600tmp * a[1]→ 120b[0] * 1201201×120 120最终b [120, 60, 40, 30, 24]与期望输出一致。4. 三语言解题代码仓库源码逐行解析以下代码均取自 LeetCode-Book 仓库sword_for_offer/codes目录文件头部带有创建时间与作者信息并内置测试用例驱动可直接编译运行。4.1 Python来自 sfo_66_a_product_array_puzzle_s1.pyclass 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.javapublic 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.cppvectorint constructArr(vectorint a) { int len a.size(); if (len 0) return {}; vectorint 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; }要点vectorint b(len, 1)利用构造函数一次性把len个元素全部填 1等价于 Python 的[1] * len(a)这是 C 版本最不易出错的初始化方式。4.4 三语言实现差异小结差异点PythonJavaC空数组处理循环天然为空无需判空显式if (len 0)返回空数组显式if (len 0)返回{}b初始化为全 1[1] * len(a)需手动b[0] 1默认值 0vectorint b(len, 1)反向遍历写法range(len(a)-2, -1, -1)for (i len-2; i 0; i--)同 Java三个版本在 测试用例 上保持一致输入{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[i1]再乘回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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考