1. 问题背景与核心需求春节假期是程序员们集中刷题提升算法能力的高峰期LeetCode热题100作为经典题库中的精华部分尤其受到关注。第238题除自身以外数组的乘积看似简单实则考察了对数组操作的深刻理解和空间优化技巧。题目要求给定一个整数数组nums返回一个数组answer其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。题目明确要求不能使用除法运算时间复杂度必须控制在O(n)空间复杂度除输出数组外应为O(1)注意这是典型的前缀积问题变种看似可以通过先计算总乘积再除以当前元素得到答案但题目禁用除法运算且当存在0元素时这种解法会失效。2. 暴力解法与优化思路2.1 直观暴力解法分析最直接的思路是对每个元素nums[i]遍历数组计算其他所有元素的乘积def productExceptSelf(nums): n len(nums) answer [1] * n for i in range(n): for j in range(n): if j ! i: answer[i] * nums[j] return answer这种解法的时间复杂度为O(n²)无法满足题目要求。我们需要寻找更高效的算法。2.2 前缀积与后缀积的启发观察发现每个answer[i]可以分解为nums[0] × nums[1] × ... × nums[i-1]左侧乘积nums[i1] × nums[i2] × ... × nums[n-1]右侧乘积这提示我们可以分别计算每个元素的前缀积和后缀积然后将两者相乘得到最终结果。3. 空间优化解法实现3.1 双数组辅助解法先使用两个辅助数组分别存储前缀积和后缀积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 i in range(n-2, -1, -1): right[i] right[i1] * nums[i1] # 合并结果 for i in range(n): answer[i] left[i] * right[i] return answer这种解法时间复杂度为O(n)但使用了两个额外数组空间复杂度为O(n)仍不满足题目对空间的要求。3.2 终极空间优化方案我们可以利用输出数组answer来存储前缀积然后通过一个变量动态计算后缀积def productExceptSelf(nums): n len(nums) answer [1] * n # 先存储前缀积到answer中 for i in range(1, n): answer[i] answer[i-1] * nums[i-1] # 使用R变量动态计算后缀积 R 1 for i in range(n-1, -1, -1): answer[i] answer[i] * R R * nums[i] return answer这个版本时间复杂度O(n)两次遍历空间复杂度除输出数组外只使用了常数空间O(1)4. 边界条件与测试案例4.1 特殊输入处理需要考虑的特殊情况包括空数组应返回空数组单元素数组按题意应返回[1]包含0的数组需要正确处理大数情况注意乘积溢出Python无需考虑但其他语言如Java/C需要注意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 时间复杂度分析算法执行两次独立的数组遍历第一次计算前缀积n-1次乘法第二次计算后缀积并合并结果n次乘法和n次乘法 总操作次数为3n-1时间复杂度为O(n)5.2 空间复杂度证明除输出数组外只使用了一个变量R存储后缀积循环变量i 因此额外空间为O(1)6. 同类问题扩展6.1 变种问题示例允许使用除法的情况如何处理计算总乘积时需注意0的个数如果有超过1个0结果数组全为0如果恰好1个0只有该位置不为0如果要求计算三个方向左、右、自身的乘积可以扩展为三维前缀积问题6.2 实际应用场景这类前缀积算法在以下场景有实际应用图像处理中的邻域计算金融数据分析中的滚动乘积计算信号处理中的滑动窗口乘积7. 编码实现细节与优化7.1 Python实现技巧def productExceptSelf(nums): n len(nums) answer [1] * n # 前缀积计算可以简化为 prefix 1 for i in range(n): answer[i] prefix prefix * nums[i] # 后缀积计算同理 suffix 1 for i in range(n-1, -1, -1): answer[i] * suffix suffix * nums[i] return answer7.2 其他语言注意事项对于C/Java等静态类型语言注意整数溢出问题可能需要使用long类型数组初始化方式不同循环索引的处理需要更谨慎8. 常见错误与调试技巧8.1 典型错误模式边界处理不当忘记处理空数组情况单元素数组返回错误结果索引越界后缀积计算时初始索引设置错误循环终止条件不正确乘积初始化错误前缀/后缀积初始值不为18.2 调试建议打印中间结果在计算前缀积和后缀积时打印辅助数组检查每一步的乘积是否正确小规模测试先用长度为2-3的数组测试逐步增加复杂度可视化分析在纸上画出计算过程标记每个步骤的乘积来源9. 春节刷题策略建议春节期间集中刷题时针对这类数组处理问题建议先理解问题本质不要急于编码从暴力解法开始逐步优化注意空间复杂度的优化往往比时间复杂度更难同类问题集中练习如前缀和、滑动窗口等每道题至少尝试两种不同的解法这道除自身以外数组的乘积作为热题100中的经典题目很好地训练了对数组操作和空间优化的理解。掌握其核心思路后可以举一反三解决更多类似的前缀/后缀计算问题。在实际面试中面试官可能会要求解释算法选择的理由和优化过程因此理解每一步的思考过程比记住解法更重要。
