2026/9/10 17:24:09
FEATURED · 精选文章 
1. 问题背景与核心挑战Leetcode 238题除自身以外数组的乘积是一个经典的数组处理问题要求我们计算一个新数组output其中output[i]等于原数组中除nums[i]之外所有元素的乘积。这个看似简单的问题实际上隐藏着几个关键的技术挑战时间复杂度限制题目明确要求不能使用除法运算且需要在O(n)时间复杂度内完成空间复杂度优化进阶要求提出能否在O(1)额外空间复杂度下完成输出数组不计入空间复杂度边界条件处理需要考虑数组长度为1的特殊情况以及乘积可能导致的整数溢出问题我在第一次遇到这个问题时尝试了最直观的暴力解法——对于每个元素都遍历整个数组计算乘积。虽然这种方法逻辑简单但时间复杂度达到了O(n²)显然无法满足题目要求。这促使我深入思考更优的解决方案。2. 前缀积与后缀积的分解思路2.1 左右乘积数组法经过研究我发现这个问题可以通过分解为前缀积和后缀积来解决。具体思路是对于数组中的每个元素nums[i]其对应的output[i]可以看作左侧所有元素的乘积prefix[i]右侧所有元素的乘积suffix[i]两者的乘积即为结果实现步骤初始化两个数组left和right大小与nums相同计算left数组left[i] left[i-1] * nums[i-1]从左到右遍历计算right数组right[i] right[i1] * nums[i1]从右到左遍历最终结果output[i] left[i] * right[i]这种方法的时间复杂度为O(n)空间复杂度也是O(n)不包括输出数组。虽然满足了基本要求但仍有优化空间。注意在实现时left[0]和right[n-1]需要初始化为1因为它们没有左侧或右侧元素2.2 空间优化版本为了达到O(1)空间复杂度的进阶要求不考虑输出数组我们可以利用输出数组本身来存储中间结果首先将output数组用作left数组初始化output[0] 1output[i] output[i-1] * nums[i-1]从左到右然后引入一个变量R来累积右侧乘积初始化R 1从右到左遍历output[i] output[i] * RR R * nums[i]这种方法巧妙地将空间复杂度降到了O(1)同时保持了O(n)的时间复杂度。在实际编码面试中这种解法往往能获得面试官的青睐。3. 具体实现与代码示例3.1 Python实现def productExceptSelf(nums): n len(nums) output [1] * n # 计算左侧乘积 for i in range(1, n): output[i] output[i-1] * nums[i-1] # 计算右侧乘积并合并结果 R 1 for i in range(n-1, -1, -1): output[i] output[i] * R R * nums[i] return output3.2 Java实现public int[] productExceptSelf(int[] nums) { int n nums.length; int[] output new int[n]; output[0] 1; for (int i 1; i n; i) { output[i] output[i-1] * nums[i-1]; } int R 1; for (int i n-1; i 0; i--) { output[i] output[i] * R; R * nums[i]; } return output; }3.3 边界条件处理在实际编码中有几个边界条件需要特别注意空数组或单元素数组空数组应返回空数组单元素数组应返回[1]因为没有其他元素可乘零值处理当数组中有多个零时所有output元素都应为0只有一个零时只有该位置的output不为零大数溢出虽然题目没有明确说明但在实际应用中需要考虑乘积可能超出整数范围的情况4. 复杂度分析与变种问题4.1 时间复杂度分析两种解法的时间复杂度都是O(n)因为都需要两次完整的数组遍历一次从左到右一次从右到左每个元素只被访问固定次数2-3次4.2 空间复杂度对比基本解法O(n)额外空间left和right数组优化解法O(1)额外空间仅使用变量R4.3 相关变种问题掌握了这个问题的解法后可以尝试解决以下类似问题允许使用除法的情况计算所有子数组的乘积计算除自身外的累加和二维矩阵版本的类似问题5. 实际应用场景这个问题虽然来自算法题库但其核心思想在实际开发中有广泛应用信号处理在数字信号处理中经常需要计算窗口内除当前点外的统计量推荐系统计算用户对某商品的评分时可能需要排除该用户自身评分的影响数据分析计算某指标的贡献度时可能需要排除特定因素的影响图像处理某些滤波算法需要计算邻域像素的某种聚合值6. 常见错误与调试技巧在实现这个算法时新手常犯的错误包括初始化错误忘记将output[0]初始化为1忘记将R初始化为1边界处理不当没有正确处理数组长度为1的情况遍历时索引越界乘积顺序错误在优化解法中先更新R再计算output[i]会导致错误调试技巧对于小数组如[1,2,3,4]手动计算预期结果打印中间变量left数组和R值验证计算过程使用Leetcode的测试用例功能检查边界情况7. 性能优化与语言特性在不同编程语言中这个算法的实现可以进一步优化Python使用numpy数组可以加速数值计算考虑使用itertools.accumulate计算前缀积Java使用System.arraycopy可能比手动循环更快考虑使用并行流处理大型数组C使用STL算法如partial_sum考虑使用SIMD指令加速乘积计算8. 数学视角的深入理解从数学角度看这个问题可以抽象为给定数组nums求数组output使得 output[i] Π(nums[0..i-1]) × Π(nums[i1..n-1])这实际上是数组元素的全乘积除以当前元素虽然题目禁止使用除法。理解这一点有助于我们设计出更通用的解决方案。9. 扩展思考多维情况如果问题扩展到二维矩阵要求计算每个元素所在行和列之外所有元素的乘积我们可以分别计算每行和每列的乘积使用类似的左右分解思路最终结果为行乘积 × 列乘积 / 当前元素如果允许除法这种思路在图像处理和科学计算中有实际应用价值。
LeetCode 238题：前缀积与后缀积优化解法详解
1. 问题背景与核心挑战Leetcode 238题除自身以外数组的乘积是一个经典的数组处理问题要求我们计算一个新数组output其中output[i]等于原数组中除nums[i]之外所有元素的乘积。这个看似简单的问题实际上隐藏着几个关键的技术挑战时间复杂度限制题目明确要求不能使用除法运算且需要在O(n)时间复杂度内完成空间复杂度优化进阶要求提出能否在O(1)额外空间复杂度下完成输出数组不计入空间复杂度边界条件处理需要考虑数组长度为1的特殊情况以及乘积可能导致的整数溢出问题我在第一次遇到这个问题时尝试了最直观的暴力解法——对于每个元素都遍历整个数组计算乘积。虽然这种方法逻辑简单但时间复杂度达到了O(n²)显然无法满足题目要求。这促使我深入思考更优的解决方案。2. 前缀积与后缀积的分解思路2.1 左右乘积数组法经过研究我发现这个问题可以通过分解为前缀积和后缀积来解决。具体思路是对于数组中的每个元素nums[i]其对应的output[i]可以看作左侧所有元素的乘积prefix[i]右侧所有元素的乘积suffix[i]两者的乘积即为结果实现步骤初始化两个数组left和right大小与nums相同计算left数组left[i] left[i-1] * nums[i-1]从左到右遍历计算right数组right[i] right[i1] * nums[i1]从右到左遍历最终结果output[i] left[i] * right[i]这种方法的时间复杂度为O(n)空间复杂度也是O(n)不包括输出数组。虽然满足了基本要求但仍有优化空间。注意在实现时left[0]和right[n-1]需要初始化为1因为它们没有左侧或右侧元素2.2 空间优化版本为了达到O(1)空间复杂度的进阶要求不考虑输出数组我们可以利用输出数组本身来存储中间结果首先将output数组用作left数组初始化output[0] 1output[i] output[i-1] * nums[i-1]从左到右然后引入一个变量R来累积右侧乘积初始化R 1从右到左遍历output[i] output[i] * RR R * nums[i]这种方法巧妙地将空间复杂度降到了O(1)同时保持了O(n)的时间复杂度。在实际编码面试中这种解法往往能获得面试官的青睐。3. 具体实现与代码示例3.1 Python实现def productExceptSelf(nums): n len(nums) output [1] * n # 计算左侧乘积 for i in range(1, n): output[i] output[i-1] * nums[i-1] # 计算右侧乘积并合并结果 R 1 for i in range(n-1, -1, -1): output[i] output[i] * R R * nums[i] return output3.2 Java实现public int[] productExceptSelf(int[] nums) { int n nums.length; int[] output new int[n]; output[0] 1; for (int i 1; i n; i) { output[i] output[i-1] * nums[i-1]; } int R 1; for (int i n-1; i 0; i--) { output[i] output[i] * R; R * nums[i]; } return output; }3.3 边界条件处理在实际编码中有几个边界条件需要特别注意空数组或单元素数组空数组应返回空数组单元素数组应返回[1]因为没有其他元素可乘零值处理当数组中有多个零时所有output元素都应为0只有一个零时只有该位置的output不为零大数溢出虽然题目没有明确说明但在实际应用中需要考虑乘积可能超出整数范围的情况4. 复杂度分析与变种问题4.1 时间复杂度分析两种解法的时间复杂度都是O(n)因为都需要两次完整的数组遍历一次从左到右一次从右到左每个元素只被访问固定次数2-3次4.2 空间复杂度对比基本解法O(n)额外空间left和right数组优化解法O(1)额外空间仅使用变量R4.3 相关变种问题掌握了这个问题的解法后可以尝试解决以下类似问题允许使用除法的情况计算所有子数组的乘积计算除自身外的累加和二维矩阵版本的类似问题5. 实际应用场景这个问题虽然来自算法题库但其核心思想在实际开发中有广泛应用信号处理在数字信号处理中经常需要计算窗口内除当前点外的统计量推荐系统计算用户对某商品的评分时可能需要排除该用户自身评分的影响数据分析计算某指标的贡献度时可能需要排除特定因素的影响图像处理某些滤波算法需要计算邻域像素的某种聚合值6. 常见错误与调试技巧在实现这个算法时新手常犯的错误包括初始化错误忘记将output[0]初始化为1忘记将R初始化为1边界处理不当没有正确处理数组长度为1的情况遍历时索引越界乘积顺序错误在优化解法中先更新R再计算output[i]会导致错误调试技巧对于小数组如[1,2,3,4]手动计算预期结果打印中间变量left数组和R值验证计算过程使用Leetcode的测试用例功能检查边界情况7. 性能优化与语言特性在不同编程语言中这个算法的实现可以进一步优化Python使用numpy数组可以加速数值计算考虑使用itertools.accumulate计算前缀积Java使用System.arraycopy可能比手动循环更快考虑使用并行流处理大型数组C使用STL算法如partial_sum考虑使用SIMD指令加速乘积计算8. 数学视角的深入理解从数学角度看这个问题可以抽象为给定数组nums求数组output使得 output[i] Π(nums[0..i-1]) × Π(nums[i1..n-1])这实际上是数组元素的全乘积除以当前元素虽然题目禁止使用除法。理解这一点有助于我们设计出更通用的解决方案。9. 扩展思考多维情况如果问题扩展到二维矩阵要求计算每个元素所在行和列之外所有元素的乘积我们可以分别计算每行和每列的乘积使用类似的左右分解思路最终结果为行乘积 × 列乘积 / 当前元素如果允许除法这种思路在图像处理和科学计算中有实际应用价值。 
