当前位置：首页 > news >正文

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

news 2026/5/24 4:22:45

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]，因为 234=24，134=12，124=12，123=6。

问题特点

这道题的关键挑战是时间复杂度要求 O(n) 和不使用除法的限制。如果允许 O(n²) 的时间，可以对每个位置遍历其他所有元素计算乘积。如果允许除法，可以先计算总乘积再除以每个元素。

前缀积与后缀积的方法通过两次线性遍历就解决了问题。第一次遍历从左到右，计算每个位置左侧所有元素的乘积；第二次遍历从右到左，计算每个位置右侧所有元素的乘积，并与左侧乘积相乘得到最终结果。

直观理解

对于位置 i 的结果，可以看作：nums[0] * nums[1] * ... * nums[i-1] * nums[i+1] * ... * 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] = 1，L[i] = L[i-1] * nums[i-1]。

在代码中，我们遍历数组，第一次填充 answer[i] 为 L[i]。

右侧乘积计算

对于位置 i 的右侧乘积 R[i] = nums[i+1] * nums[i+2] * ... * nums[n-1]。同样可以通过递推计算：R[n-1] = 1，R[i] = R[i+1] * nums[i+1]。

在代码中，我们从右向左遍历，使用一个变量累积右侧乘积，并与 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 answer

Java 实现

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] = 1，product 保持为 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("所有测试用例通过！")