LeetCode 238题：除自身以外数组乘积的O(n)解法

1. 题目解析与核心思路

238题"除自身以外数组的乘积"是LeetCode中经典的数组处理问题。题目要求：给定一个整数数组nums，返回一个数组answer，其中answer[i]等于nums中除nums[i]之外所有元素的乘积。题目特别强调不能使用除法运算，且在O(n)时间复杂度内完成。

1.1 问题示例分析

以nums = [1,2,3,4]为例：

• answer[0] = 2×3×4 = 24
• answer[1] = 1×3×4 = 12
• answer[2] = 1×2×4 = 8
• answer[3] = 1×2×3 = 6 最终输出应为[24,12,8,6]

1.2 暴力解法与局限

最直观的解法是对于每个元素，遍历数组计算其他元素的乘积。这种方法时间复杂度为O(n²)，无法满足题目要求。另一种思路是先计算所有元素的乘积，然后对每个元素用总积除以当前元素值，但这违反了题目禁止使用除法的限制。

2. 前缀积与后缀积算法

2.1 核心算法思想

高效解法基于前缀积和后缀积的概念：

1. 前缀积：left[i]表示nums[0]到nums[i-1]的乘积
2. 后缀积：right[i]表示nums[i+1]到nums[n-1]的乘积
3. 结果数组：answer[i] = left[i] * right[i]

2.2 空间优化实现

实际上可以优化空间复杂度到O(1)（不包括输出数组）：

def productExceptSelf(nums): n = len(nums) answer = [1] * n # 计算左侧乘积 for i in range(1, n): answer[i] = answer[i-1] * nums[i-1] # 计算右侧乘积并合并结果 right = 1 for i in range(n-1, -1, -1): answer[i] *= right right *= nums[i] return answer

3. 算法步骤详解

3.1 左侧乘积计算

初始化answer数组全为1。从左到右遍历：

• answer[0] = 1（第一个元素左侧无元素）
• answer[1] = nums[0]
• answer[2] = nums[0]×nums[1]
• ...
• answer[i] = nums[0]×...×nums[i-1]

3.2 右侧乘积计算

从右到左遍历，维护一个right变量：

• 初始right = 1
• answer[n-1] *= right (即保持不变)
• right *= nums[n-1]
• answer[n-2] *= right (即乘以nums[n-1])
• right *= nums[n-2]
• ...
• answer[i] *= right (即乘以nums[i+1]×...×nums[n-1])

4. 边界条件与特殊处理

4.1 零值处理

当数组中有0时：

• 如果有两个及以上0，所有结果都为0
• 如果只有一个0，只有该位置的结果不为0 算法自动处理了这些情况，无需特殊判断

4.2 大数溢出

虽然题目未明确说明，但在实际应用中需要考虑：

• Python整数不会溢出
• 其他语言如Java/C++可能需要使用long类型
• 可以添加模数运算（如10^9+7）防止溢出

5. 复杂度分析与变种

5.1 时间复杂度

• 两次遍历数组：O(n) + O(n) = O(n)
• 满足题目要求

5.2 空间复杂度

• 输出数组不计入空间复杂度
• 只使用了常数空间：O(1)

5.3 类似题目变种

1. 允许使用除法的情况
2. 多维数组的乘积问题
3. 流式数据下的乘积计算

6. 实际应用场景

这种前缀/后缀积的思想广泛应用于：

• 图像处理中的滤波器设计
• 金融领域的移动平均计算
• 信号处理中的卷积运算
• 数据库查询优化

提示：面试中常被用作考察候选人数组处理能力和空间优化思维的典型题目。建议熟练掌握并能够解释每个步骤的数学原理。

7. 常见错误与调试技巧

7.1 典型错误模式

1. 边界处理不当：

   • 忘记初始化answer[0] = 1
   • 右侧乘积遍历时索引越界

2. 空间使用错误：

   • 不必要地使用了额外的left/right数组
   • 没有利用输出数组进行中间存储

7.2 调试建议

1. 小规模测试用例：

   • 空数组[]
   • 单元素数组[5]
   • 包含0的数组[0,1,2]

2. 打印中间变量：

   print(f"i={i}, answer={answer}, right={right}")

8. 不同语言实现对比

8.1 Java实现

public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; Arrays.fill(answer, 1); for (int i = 1; i < n; i++) { answer[i] = answer[i-1] * nums[i-1]; } int right = 1; for (int i = n-1; i >= 0; i--) { answer[i] *= right; right *= nums[i]; } return answer; }

8.2 C++实现

vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> answer(n, 1); for (int i = 1; i < n; i++) { answer[i] = answer[i-1] * nums[i-1]; } int right = 1; for (int i = n-1; i >= 0; i--) { answer[i] *= right; right *= nums[i]; } return answer; }

9. 算法优化与扩展

9.1 并行计算优化

对于超大数组，可以考虑：

• 将数组分块
• 并行计算各块的前缀/后缀积
• 合并各块结果

9.2 流式处理版本

当数据以流形式到达时：

• 维护运行乘积
• 使用队列保存最近k个元素
• 动态更新结果

10. 数学原理深入

10.1 乘积分解原理

算法本质是将乘积分解为： product = left × right 其中left和right可以递推计算： left[i] = left[i-1] × nums[i-1] right[i] = right[i+1] × nums[i+1]

10.2 不变式分析

在右侧乘积计算时，维护的不变式是： right始终等于nums[i+1]×...×nums[n-1] 因此answer[i] = left[i] × right

11. 面试技巧与注意事项

1. 明确问题要求：

   • 确认是否可以修改输入数组
   • 确认输出数组是否计入空间复杂度

2. 分步解释思路：

   • 先提出暴力解法
   • 分析其不足
   • 逐步优化到最终方案

3. 测试用例设计：

   • 常规情况
   • 边界情况（空数组、单元素）
   • 特殊值（包含0、负数）

12. 实际编码建议

1. 变量命名：

   • 使用left_product/right_product代替简单的left/right
   • 使用n代替len(nums)提高可读性

2. 代码风格：

   • 添加适当的空行分隔逻辑块
   • 关键步骤添加注释

3. 防御性编程：

   • 检查输入数组是否为空
   • 考虑整数溢出情况

13. 可视化理解

以nums = [1,2,3,4]为例：

初始: answer = [1, 1, 1, 1] 左侧计算: i=1: answer = [1, 1×1, 1, 1] = [1,1,1,1] i=2: answer = [1,1, 1×2,1] = [1,1,2,1] i=3: answer = [1,1,2, 2×3] = [1,1,2,6] 右侧计算: i=3: answer = [1,1,2,6×1], right=1×4=4 i=2: answer = [1,1,2×4,6], right=4×3=12 i=1: answer = [1,12×1,8,6], right=12×2=24 i=0: answer = [1×24,12,8,6], right=24×1=24 最终结果: [24,12,8,6]

14. 性能测试与比较

测试不同规模数组下的运行时间（Python）：

15. 进阶思考题

1. 如果允许使用除法，算法如何简化？时间复杂度如何变化？
2. 如何修改算法，使其适用于矩阵的类似计算？
3. 如果要求同时计算除i和j以外所有元素的乘积（i≠j），如何设计算法？
4. 在分布式环境下，如何实现这个算法？

16. 历史背景与相关研究

前缀积算法是前缀和算法的自然扩展，最早出现在1973年APL语言的研究中。类似思想在：

• 并行计算中的scan操作
• 函数式编程中的fold操作
• 数据库中的窗口函数

17. 实际工程应用案例

1. 推荐系统中的协同过滤：

   • 计算用户相似度时排除当前用户
   • 计算物品相似度时排除当前物品

2. 时间序列分析：

   • 计算移动平均时排除当前点
   • 异常检测中的局部统计量计算

3. 图像处理：

   • 局部对比度增强
   • 邻域像素统计

18. 不同解法性能对比

除了前缀积/后缀积方法，还有其他解法：

19. 代码测试与验证

完整测试用例集：

test_cases = [ ([1,2,3,4], [24,12,8,6]), ([0,1,2,3], [6,0,0,0]), ([1,0], [0,1]), ([5], [1]), ([], []), ([1,-1,1,-1,1], [-1,1,-1,1,-1]) ] for nums, expected in test_cases: assert productExceptSelf(nums) == expected, f"Failed for {nums}" print("All tests passed!")

20. 总结与个人心得

在实际刷题和面试中，这类数组处理问题考验的是对问题本质的洞察力。我总结出几个关键点：

1. 画图辅助：用简单的例子（如4元素数组）在纸上画出计算过程，能快速发现规律
2. 分步思考：先解决部分问题（如只算左侧乘积），再逐步完善
3. 空间优化：总是思考能否复用已有空间，减少额外存储
4. 边界检查：特别注意空数组、单元素数组等边界情况

这个算法最精妙之处在于利用输出数组存储中间结果，实现了空间复杂度的优化。这种"空间复用"的思想在很多算法问题中都有体现，值得深入理解和掌握。