LeetCode 238：除自身以外数组的乘积 | 前缀积与后缀积

LeetCode 238除自身以外数组的乘积 | 前缀积与后缀积引言除自身以外数组的乘积Product of Array Except Self是 LeetCode 第 238 题难度为 Medium。题目要求在 O(n) 时间内不使用除法计算每个元素除自身以外所有其他元素的乘积。这道题展示了前缀积与后缀积的巧妙应用是一种典型的空间换时间和时间换空间的权衡。问题的核心挑战在于如何在不使用除法的情况下计算每个位置的结果。如果可以使用除法只需要一次遍历计算所有元素的乘积然后对每个位置返回 total_product / nums[i] 即可。但除法可能带来精度问题和溢出问题因此题目要求不使用除法。前缀积与后缀积的方法巧妙地解决了这个问题。问题分析题目描述给定一个整数数组 nums返回一个数组 answer其中 answer[i] 等于 nums 中除 nums[i] 之外其余所有元素的乘积。要求不使用除法且时间复杂度为 O(n)。例如输入 nums [1,2,3,4]输出 answer [24,12,8,6]因为 2342413412124121236。问题特点这道题的关键挑战是时间复杂度要求 O(n) 和不使用除法的限制。如果允许 O(n²) 的时间可以对每个位置遍历其他所有元素计算乘积。如果允许除法可以先计算总乘积再除以每个元素。前缀积与后缀积的方法通过两次线性遍历就解决了问题。第一次遍历从左到右计算每个位置左侧所有元素的乘积第二次遍历从右到左计算每个位置右侧所有元素的乘积并与左侧乘积相乘得到最终结果。直观理解对于位置 i 的结果可以看作nums[0] * nums[1] * ... * nums[i-1] * nums[i1] * ... * nums[n-1]即左侧所有元素的乘积乘以右侧所有元素的乘积。如果我们能预先计算出每个位置左侧和右侧的乘积就可以 O(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[i 1] * nums[i 1] for i in range(n): answer[i] left[i] * right[i] return answer这个方法使用两个额外的数组 left 和 right 分别存储每个位置左侧和右侧的乘积然后合并得到结果。方法二空间优化def productExceptSelf_optimized(nums): n len(nums) answer [1] * n for i in range(1, n): answer[i] answer[i - 1] * nums[i - 1] product 1 for i in range(n - 2, -1, -1): product * nums[i 1] answer[i] * product return answer空间优化版本只使用一个 answer 数组。第一次遍历填充左侧乘积第二次遍历在原数组上累积右侧乘积并与 answer 中的左侧乘积相乘。方法三双指针def productExceptSelf_two_pointer(nums): n len(nums) answer [1] * n left right 1 for i in range(n): if i 0: left * nums[i - 1] answer[i] * left for i in range(n - 1, -1, -1): if i n - 1: right * nums[i 1] answer[i] * right return answer双指针方法同时从左到右和从右到左遍历使用 left 和 right 变量分别累积左右乘积。算法详解左侧乘积计算对于位置 i 的左侧乘积 L[i] nums[0] * nums[1] * ... * nums[i-1]。这个可以通过递推计算L[0] 1L[i] L[i-1] * nums[i-1]。在代码中我们遍历数组第一次填充 answer[i] 为 L[i]。右侧乘积计算对于位置 i 的右侧乘积 R[i] nums[i1] * nums[i2] * ... * nums[n-1]。同样可以通过递推计算R[n-1] 1R[i] R[i1] * nums[i1]。在代码中我们从右向左遍历使用一个变量累积右侧乘积并与 answer 中的左侧乘积相乘。为什么不需要除法因为我们分别计算了左侧和右侧的乘积最后将它们相乘就得到了除自身以外所有元素的乘积。这个过程不需要除法避免了精度问题和溢出问题。复杂度分析时间复杂度时间复杂度为 O(n)因为我们进行了两次线性遍历。每次遍历都是 O(n)总共 O(n)。空间复杂度方法一使用了三个额外的数组空间复杂度为 O(n)。方法二和方法三将空间复杂度降低到 O(1)除了输入和输出数组。代码实现Python 实现def productExceptSelf(nums): n len(nums) answer [1] * n for i in range(1, n): answer[i] answer[i - 1] * nums[i - 1] product 1 for i in range(n - 2, -1, -1): product * nums[i 1] answer[i] * product return answerJava 实现public int[] productExceptSelf(int[] nums) { int n nums.length; int[] answer new int[n]; answer[0] 1; for (int i 1; i n; i) { answer[i] answer[i - 1] * nums[i - 1]; } int product 1; for (int i n - 2; i 0; i--) { product * nums[i 1]; answer[i] * product; } return answer; }边界情况处理空数组当数组为空时无法计算有意义的结果通常返回空数组。代码会正确处理因为循环不会执行。单个元素当数组只有一个元素时根据定义应该返回 [1]只有自身以外的空乘积。代码中answer[0] 1product 保持为 1因为内层循环不执行返回 [1]。包含零的情况当数组包含零时如果只有一个零那么除该位置以外的乘积都是零。如果有两个或更多零除这两个位置以外的乘积不为零但很可能是零。算法正确处理了这些情况因为乘法天然支持零。全零情况当所有元素都是零时根据定义除自身以外所有元素的乘积都是零因为其他元素都是零。算法正确处理了这种情况。溢出问题在 Java 等语言中乘积可能超出整数范围。LeetCode 的测试用例通常在合理范围内设计但在某些情况下可能需要使用 long 类型来处理溢出。在 Python 中整数可以自动扩展没有这个问题。测试用例def test_product_except_self(): assert productExceptSelf([1, 2, 3, 4]) [24, 12, 8, 6] assert productExceptSelf([1, 2]) [2, 1] assert productExceptSelf([1]) [1] assert productExceptSelf([0, 1]) [1, 0] assert productExceptSelf([0, 0]) [0, 0] assert productExceptSelf([1, 0, 3]) [0, 3, 0] assert productExceptSelf([2, 3, 4, 5]) [60, 40, 30, 24] print(所有测试用例通过)扩展问题不能使用额外空间如果严格要求 O(1) 额外空间不包括输出数组空间优化版本的方法二和三都满足要求只需要常数个额外变量。返回乘积的数组而不是数组如果题目要求返回乘积的数组如 [2, 3, 4, 5] - [60, 40, 30, 24]算法不变直接返回 answer 数组即可。乘积很大需要取模如果乘积很大需要取模如 10^9 7需要在每次乘法后取模。实际应用场景除自身以外数组的乘积问题在现实中有很多应用。在金融领域可以用来计算投资组合中某个资产之外的其他资产的综合收益率。在信号处理中可以用来计算频谱分析中某个频率分量之外的能量。在数学中这种运算与卷积和多项式乘法有密切关系。前缀积与后缀积的思想也可以推广到其他类似问题如前缀最大值、后缀最大值等。总结除自身以外数组的乘积问题展示了前缀积与后缀积的巧妙应用。通过分别计算每个位置左侧和右侧的乘积我们可以 O(n) 时间内解决看似需要除法的问题。这个问题的关键洞察是对于位置 i 的结果 左侧所有元素的乘积 × 右侧所有元素的乘积。分别计算这两个乘积再相乘就得到了最终结果。希望通过本文的讲解读者能够掌握前缀积与后缀积的思想并将其应用到更多类似问题的解决中。