LeetCode数组乘积问题：O(n)时间复杂度解法详解-迪斯科星球

1. 问题解析：LeetCode Hot100 T238 数组乘积问题

这道题目要求我们实现一个算法，计算数组中每个元素除自身外其他所有元素的乘积。题目明确要求：

时间复杂度必须控制在O(n)
不能使用除法运算
空间复杂度除输出数组外应为O(1)

1.1 核心难点分析

这道题的难点主要在于三个限制条件的组合：

禁止使用除法运算：排除了先计算总乘积再除以当前元素的取巧方案
线性时间复杂度：要求我们只能进行有限次数的数组遍历
常数空间复杂度：限制了额外数据结构的使用

提示：在实际面试中，面试官提出这些限制条件是为了考察对前缀/后缀乘积的理解和应用能力。

2. 解决方案设计与思路拆解

2.1 双指针乘积法

最优解采用左右乘积列表的思路，通过两次遍历实现：

第一次从左到右遍历，计算每个元素左侧所有元素的乘积
第二次从右到左遍历，计算每个元素右侧所有元素的乘积
将左右乘积相乘得到最终结果

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

2.2 空间优化技巧

虽然题目允许输出数组不计入空间复杂度，但我们仍可以进一步优化：

使用输出数组直接存储左侧乘积
在计算右侧乘积时，使用单个变量动态维护右侧乘积

def productExceptSelf(nums): n = len(nums) res = [1] * n # 左侧乘积直接存入res for i in range(1, n): res[i] = res[i-1] * nums[i-1] # 右侧乘积使用变量维护 right = 1 for i in range(n-1, -1, -1): res[i] *= right right *= nums[i] return res

3. 算法复杂度分析

3.1 时间复杂度

无论采用哪种实现方式，算法都只进行了两次线性遍历：

第一次遍历：O(n)
第二次遍历：O(n)
总时间复杂度：O(2n) = O(n)

3.2 空间复杂度

优化后的方案：

输出数组不计入空间复杂度
仅使用常数个额外变量（left, right等）
实际空间复杂度：O(1)

4. 边界条件与特殊测试用例

4.1 必须考虑的边界情况

空数组输入：应返回空数组
单元素数组：根据题意应返回[1]
包含0的数组：
- 单个0：[0,1] → [1,0]
- 多个0：[0,0] → [0,0]

4.2 典型测试用例示例

test_cases = [ ([1,2,3,4], [24,12,8,6]), ([-1,1,0,-3,3], [0,0,9,0,0]), ([0,0], [0,0]), ([1], [1]), ([], []) ]

5. 同类问题扩展与变种

5.1 允许使用除法的解法

如果取消除法限制，可以这样实现：

def productExceptSelf(nums): total = 1 zero_count = 0 for num in nums: if num == 0: zero_count += 1 continue total *= num res = [] for num in nums: if zero_count > 1: res.append(0) elif zero_count == 1: res.append(0 if num != 0 else total) else: res.append(total // num) return res

5.2 三维乘积问题扩展

考虑三维数组版本，计算每个元素在三个维度上的乘积：

def product3DExceptSelf(matrix): m, n, p = len(matrix), len(matrix[0]), len(matrix[0][0]) res = [[[1 for _ in range(p)] for _ in range(n)] for _ in range(m)] # 计算x方向乘积 for i in range(m): for j in range(n): for k in range(p): if i > 0: res[i][j][k] *= res[i-1][j][k] * matrix[i-1][j][k] # 计算y方向乘积 # ...类似实现其他维度... return res

6. 实际工程应用场景

6.1 图像处理中的滤波器计算

在图像卷积运算中，经常需要计算局部窗口内像素的乘积，这种算法可以优化某些特殊滤波器的实现。

6.2 金融数据分析

计算投资组合中各资产的相对表现时，可能需要排除特定资产计算其余资产的综合表现。

6.3 推荐系统

在协同过滤算法中，计算用户相似度时可能需要排除当前物品的影响。

7. 常见错误与调试技巧

7.1 典型错误模式

初始化错误：
- 忘记将res[0]初始化为1
- 错误地使用[0]*n作为初始值
边界处理不当：
- 在第二次遍历时错误的起始索引
- 处理n-1元素时数组越界
乘积顺序错误：
- 先计算右侧乘积再计算左侧乘积导致覆盖

7.2 调试建议

使用小规模测试用例手动验证
打印中间乘积结果检查计算过程
特别注意索引边界条件
对于包含0的数组要单独测试

8. 不同语言实现要点

8.1 C++实现注意事项

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

注意点：

使用vector时要预先分配空间
注意整数溢出问题，可能需要使用long long

8.2 Java实现特点

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

特点：

使用Arrays.fill初始化数组
注意Java数组是固定长度的

9. 算法优化进阶思路

9.1 并行计算优化

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

将数组分段
并行计算各段的左右乘积
合并分段结果

9.2 流式处理版本

适合数据流场景，维护动态乘积：

class StreamProduct: def __init__(self): self.products = [] self.total = 1 def add(self, num): self.products.append(self.total) self.total *= num def getProductExceptSelf(self, index): return self.products[index] * (self.total // (self.products[index] * self.nums[index]))

10. 面试技巧与答题策略

10.1 面试回答框架

明确问题要求和限制条件
提出暴力解法并分析其缺点
逐步优化思路，解释前缀/后缀乘积的概念
给出优化后的实现方案
分析时间/空间复杂度
讨论边界条件和测试用例

10.2 可能follow-up问题

如果数组特别大无法全部放入内存怎么办？
如何修改算法使其适用于链表结构？
如果允许使用除法，算法会有怎样的变化？
如何测试这个函数的正确性？

11. 数学原理深入探讨

11.1 乘积的分解性质

该算法基于乘积的分解性质： product = left_product * right_product 其中： left_product = ∏ nums[0..i-1] right_product = ∏ nums[i+1..n-1]

11.2 前缀与后缀的数学关系

本质上是在计算： res[i] = prefix[i-1] * suffix[i+1] 其中prefix和suffix可以通过动态规划递推得到

12. 可视化理解方法

12.1 图形化表示

以数组[1,2,3,4]为例：

原始数组： [1, 2, 3, 4] 左乘积： [1, 1, 2, 6] 右乘积： [24, 12, 4, 1] 结果： [24, 12, 8, 6]

12.2 动画演示思路

从左到右的扫描过程，逐步累积左侧乘积
从右到左的扫描过程，逐步累积右侧乘积
最后合并的过程

13. 历史背景与相关算法

13.1 问题起源

这类乘积问题最早出现在信号处理领域，用于计算滑动窗口内的乘积。在1980年代的图像处理论文中就有类似算法的记载。

13.2 相关算法比较

滑动窗口乘积：维护一个固定大小的窗口乘积
累加数组：计算前缀和数组的变种
分治算法：将数组分成两半分别计算

14. 实际编码注意事项

14.1 Python实现细节

列表初始化使用乘法要小心（对于可变对象不适用）
注意Python的整数不会溢出，但其他语言需要考虑
使用range时注意边界

14.2 防御性编程

添加输入验证：

if not nums: return []

处理超大数乘积（虽然Python不需要）
添加类型注解提高可读性

15. 单元测试与性能测试

15.1 单元测试样例

import unittest class TestProduct(unittest.TestCase): def test_normal_case(self): self.assertEqual(productExceptSelf([1,2,3,4]), [24,12,8,6]) def test_with_zeros(self): self.assertEqual(productExceptSelf([0,1,2]), [2,0,0]) def test_empty_input(self): self.assertEqual(productExceptSelf([]), [])

15.2 性能测试方法

import time import random def test_performance(): sizes = [10, 100, 1000, 10000] for size in sizes: nums = [random.randint(1, 100) for _ in range(size)] start = time.time() productExceptSelf(nums) print(f"Size {size}: {time.time()-start:.6f}s")

16. 算法扩展应用

16.1 对数变换解法

利用对数的性质，将乘积转换为对数和：

import math def productExceptSelf(nums): sum_log = sum(math.log10(num) for num in nums) return [round(10**(sum_log - math.log10(num))) for num in nums]

注意：此方法存在浮点精度问题，仅适用于特定场景

16.2 位运算版本

对于二进制数组（元素仅为0或1）：

def productExceptSelf(nums): total_and = 1 for num in nums: total_and &= num return [total_and if num else 0 for num in nums]

17. 多维度思考角度

17.1 从动态规划视角

可以将左右乘积看作两个状态：

left[i] = left[i-1] * nums[i-1]
right[i] = right[i+1] * nums[i+1]

17.2 从分治算法视角

将数组分成两半：

前半部分的乘积 * 后半部分的乘积
递归计算直到单个元素

18. 内存访问模式分析

18.1 缓存友好性

该算法的两次遍历都是顺序访问，具有很好的空间局部性，对CPU缓存友好。

18.2 内存占用分析

优化后的版本：

输入数组：O(n)
输出数组：O(n)（通常不计入）
临时变量：O(1)

19. 相关LeetCode题目推荐

1. 乘积最大子数组
1. 最大子序和
1. 接雨水
1. 分发糖果
1. 三个数的最大乘积

20. 个人实战经验分享

在实际编码中发现几个易错点：

初始值设置不正确导致第一个或最后一个元素错误
遍历方向错误导致乘积计算错误
处理包含0的数组时逻辑不完整

建议的编码步骤：

先写出暴力解法理解题意
画出乘积计算示意图
分步实现左右乘积计算
最后合并优化

企业官网建设流程全解析