## 1. 问题背景与核心需求 这道算法题看似简单却暗藏玄机。给定一个整数数组nums要求返回一个新数组answer其中answer[i]等于nums中除nums[i]之外所有元素的乘积。题目明确要求不能使用除法运算且时间复杂度必须控制在O(n)内。 我第一次遇到这个问题是在某大厂的面试现场当时下意识想用暴力解法但面试官紧接着追加了时间复杂度限制。这让我意识到这类题目考察的不仅是基础编码能力更是对空间换时间、预处理技巧等核心算法思维的掌握程度。 ## 2. 暴力解法与优化方向 ### 2.1 直观解法及其缺陷 最直接的思路是双层循环遍历 python def productExceptSelf(nums): n len(nums) answer [1] * n for i in range(n): for j in range(n): if i ! j: answer[i] * nums[j] return answer这种解法时间复杂度O(n²)当n1e5时计算量会达到1e10次操作完全无法接受。即使采用预先计算总乘积再除以当前元素的方法时间复杂度O(n)也因题目禁止使用除法而不可行。2.2 关键突破口分析通过绘制乘积关系图可以发现每个位置的输出实际等于其左侧所有元素的乘积乘以右侧所有元素的乘积。例如对于数组[1,2,3,4]answer[2] 左侧(1×2) × 右侧(4) 8answer[1] 左侧(1) × 右侧(3×4) 12这种左右分解的思路将问题转化为两个独立的子问题计算每个元素左侧所有元素的乘积前缀积计算每个元素右侧所有元素的乘积后缀积3. 最优解实现方案3.1 空间O(n)的标准解法def productExceptSelf(nums): n len(nums) left [1] * n right [1] * n answer [1] * n # 计算左侧乘积 for i in range(1, n): left[i] left[i-1] * nums[i-1] # 计算右侧乘积 for j in range(n-2, -1, -1): right[j] right[j1] * nums[j1] # 合并结果 for k in range(n): answer[k] left[k] * right[k] return answer这种方法需要额外的left和right数组空间复杂度O(n)。虽然满足时间复杂度要求但仍有优化空间。3.2 空间O(1)的进阶解法输出数组不计入空间def productExceptSelf(nums): n len(nums) answer [1] * n # 先用answer存储左侧乘积 for i in range(1, n): answer[i] answer[i-1] * nums[i-1] # 动态计算右侧乘积并直接相乘 right 1 for j in range(n-1, -1, -1): answer[j] * right right * nums[j] return answer这个版本的精妙之处在于第一轮遍历将answer数组变为左侧乘积第二轮从右向左遍历时用单个变量right动态维护右侧乘积省去了额外的存储空间除输出数组外4. 边界条件与特殊处理4.1 零值处理当数组包含0时需要特别注意单个0时除0位置外其他位置结果都为0多个0时所有位置结果都为0 但我们的解法天然正确处理了这些情况因为乘积计算会自然传播0值。4.2 大数溢出问题当数组元素值较大时乘积可能超出整型范围。在实际工程中需要使用Python无需担心自动大整数支持在Java/C等语言中可考虑取模运算如果题目允许添加中间结果检查5. 复杂度分析与对比解法类型时间复杂度空间复杂度适用场景暴力解法O(n²)O(1)绝对不可用标准前后缀数组O(n)O(n)教学理解优化空间版本O(n)O(1)不计输出面试最佳答案除法解法O(n)O(1)违反题目约束6. 变种问题拓展6.1 三维乘积问题如果要求计算除i,j位置外的所有元素乘积矩阵情况可以扩展思路计算每行的乘积数组row_product计算每列的乘积数组col_productanswer[i][j] row_product[i] * col_product[j] / nums[i][j]²6.2 乘积最大子数组类似思路可用于解决乘积最大子数组问题LeetCode 152通过同时维护当前最大值和最小值来应对负负得正的情况。7. 实际工程应用场景推荐系统计算特征权重时排除自身影响图像处理像素邻域运算时排除中心像素时间序列分析计算滑动窗口统计量时排除当前点金融分析计算投资组合风险时隔离单个资产影响8. 常见错误与调试技巧初始化错误忘记将answer[0]初始化为1后缀积遍历时right初始值设错索引越界处理空数组时直接访问nums[0]遍历时错用range范围调试建议# 打印中间结果 print(fStep {i}: left{left}, right{right}) # 使用断言检查 assert len(answer) len(nums)9. 不同语言实现要点9.1 Java实现注意// 注意数组初始化和类型声明 int[] answer new int[nums.length]; Arrays.fill(answer, 1);9.2 C优化技巧// 使用vector的assign方法快速初始化 vectorint answer(nums.size(), 1); // 反向遍历时注意size_t类型问题 for(int jnums.size()-2; j0; --j)10. 算法思维培养建议画图辅助绘制乘积关系示意图分治思想将问题分解为前缀和后缀两个子问题空间优化观察数据依赖关系寻找复用机会测试驱动先写测试用例再编码这个问题的精妙之处在于教会我们看似需要O(n²)时间的问题通过巧妙的预处理和空间换时间策略完全可以优化到线性时间复杂度。在实际工程中这种将复杂计算分解为多个线性扫描的模式类似MapReduce中的map阶段是非常有价值的思维模式。