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 核心算法思想

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

前缀积：left[i]表示nums[0]到nums[i-1]的乘积
后缀积：right[i]表示nums[i+1]到nums[n-1]的乘积
结果数组：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 类似题目变种

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

6. 实际应用场景

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

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

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

7. 常见错误与调试技巧

7.1 典型错误模式

边界处理不当：
- 忘记初始化answer[0] = 1
- 右侧乘积遍历时索引越界
空间使用错误：
- 不必要地使用了额外的left/right数组
- 没有利用输出数组进行中间存储

7.2 调试建议

小规模测试用例：
- 空数组[]
- 单元素数组[5]
- 包含0的数组[0,1,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. 面试技巧与注意事项

明确问题要求：
- 确认是否可以修改输入数组
- 确认输出数组是否计入空间复杂度
分步解释思路：
- 先提出暴力解法
- 分析其不足
- 逐步优化到最终方案
测试用例设计：
- 常规情况
- 边界情况（空数组、单元素）
- 特殊值（包含0、负数）

12. 实际编码建议

变量命名：
- 使用left_product/right_product代替简单的left/right
- 使用n代替len(nums)提高可读性
代码风格：
- 添加适当的空行分隔逻辑块
- 关键步骤添加注释
防御性编程：
- 检查输入数组是否为空
- 考虑整数溢出情况

13. 可视化理解