【LeetCode Hot 100】 除自身以外数组的乘积（238题）多解法详解

题目概述

题目名称：238. 除自身以外数组的乘积
难度：中等
题目链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）

题目描述：
给定一个整数数组nums，返回一个数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。

关键点：

• 不能使用除法

• 时间复杂度要求O(n)

• 空间复杂度要求O(1)（输出数组不计入空间复杂度）

示例：

text

输入: nums = [1,2,3,4] 输出: [24,12,8,6] 解释： answer[0] = 2*3*4 = 24 answer[1] = 1*3*4 = 12 answer[2] = 1*2*4 = 8 answer[3] = 1*2*3 = 6

示例 2：

text

输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]

解题思路总览

本题的核心在于：answer[i] = 左侧所有元素的乘积 × 右侧所有元素的乘积

如果不限制除法和空间复杂度，最直观的方法有两种：

1. 暴力法：对每个位置计算左右乘积 → O(n²)

2. 除法法：计算总乘积，除以nums[i]→ 但存在除零问题且题目禁止使用除法

题目要求的O(n)时间和O(1)额外空间，需要巧妙地利用输出数组本身来存储中间结果。

解法一：左右乘积数组（最直观）

核心思想

定义两个数组：

• left[i]：表示nums[i]左侧所有元素的乘积（不包括nums[i]）

• right[i]：表示nums[i]右侧所有元素的乘积（不包括nums[i]）

则answer[i] = left[i] * right[i]

算法步骤

1. 初始化left[0] = 1，从左到右遍历：left[i] = left[i-1] * nums[i-1]

2. 初始化right[n-1] = 1，从右到左遍历：right[i] = right[i+1] * nums[i+1]

3. 计算结果：answer[i] = left[i] * right[i]

代码实现（Python）

python

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) # 左侧乘积数组 left = [1] * n for i in range(1, n): left[i] = left[i-1] * nums[i-1] # 右侧乘积数组 right = [1] * n for i in range(n-2, -1, -1): right[i] = right[i+1] * nums[i+1] # 计算结果 answer = [left[i] * right[i] for i in range(n)] return answer

代码实现（Java）

java

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

复杂度分析：

• 时间复杂度：O(n)

• 空间复杂度：O(n)（使用了两个辅助数组）

解法二：空间优化版（推荐解法）

核心思想

利用输出数组answer先存储左侧乘积，然后在从右向左遍历的过程中，用一个变量rightProduct记录右侧乘积，一边遍历一边将rightProduct乘入answer[i]。

算法步骤

1. 初始化answer[0] = 1，第一遍遍历计算左侧乘积存入answer

2. 初始化rightProduct = 1，第二遍从右向左遍历：

   • answer[i] = answer[i] * rightProduct

   • rightProduct = rightProduct * nums[i]

代码实现（Python）

python

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) answer = [1] * n # 第一遍：计算左侧乘积 for i in range(1, n): answer[i] = answer[i-1] * nums[i-1] # 第二遍：乘以右侧乘积 right_product = 1 for i in range(n-1, -1, -1): answer[i] = answer[i] * right_product right_product *= nums[i] return answer

代码实现（Java）

java

class Solution { 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 rightProduct = 1; for (int i = n-1; i >= 0; i--) { answer[i] = answer[i] * rightProduct; rightProduct *= nums[i]; } return answer; } }

复杂度分析：

• 时间复杂度：O(n)

• 空间复杂度：O(1)（输出数组不计入额外空间）

解法三：单次遍历版（双指针）

核心思想

使用左右双指针同时从两端遍历，用两个变量leftProduct和rightProduct分别记录左边和右边的累积乘积。当左右指针相遇时，所有位置的结果都已计算完成。

算法步骤

1. 初始化answer数组全为 1

2. 初始化left = 0，right = n-1

3. 初始化leftProduct = 1，rightProduct = 1

4. 当left <= right时循环：

   • answer[left] *= leftProduct

   • answer[right] *= rightProduct

   • leftProduct *= nums[left]

   • rightProduct *= nums[right]

   • left++，right--

代码实现（Python）

python

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) answer = [1] * n left = 0 right = n - 1 left_product = 1 right_product = 1 while left <= right: answer[left] *= left_product answer[right] *= right_product left_product *= nums[left] right_product *= nums[right] left += 1 right -= 1 return answer

代码实现（Java）

java

class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; Arrays.fill(answer, 1); int left = 0, right = n - 1; int leftProduct = 1, rightProduct = 1; while (left <= right) { answer[left] *= leftProduct; answer[right] *= rightProduct; leftProduct *= nums[left]; rightProduct *= nums[right]; left++; right--; } return answer; } }

复杂度分析：

• 时间复杂度：O(n)

• 空间复杂度：O(1)

注意：此解法虽然代码简洁，但需要确保对数组下标的处理正确。当n为奇数时，中间元素会被乘两次（一次作为左指针，一次作为右指针），但由于初始值为 1，结果正确。

解法对比总结

面试建议：解法二是最推荐的写法，既满足题目要求（O(1) 额外空间），又清晰易懂，是面试官期望的标准答案。

易错点总结

1. 索引边界：计算左侧乘积时，answer[0] = 1，因为第一个元素左侧没有元素；右侧乘积同理。

2. 变量更新顺序：在第二遍遍历中，必须先更新answer[i]，再更新rightProduct。如果顺序颠倒，当前元素会被自己的值多乘一次。

3. 乘积溢出：虽然题目没有明确说明，但实际测试数据在 32 位整数范围内。如果考虑大数，可使用 Python（自动支持大整数）或 Java 的long类型。

4. 零的处理：此方法天然支持包含零的情况，不需要特殊处理。例如nums = [0, 1, 2]，结果应为[2, 0, 0]。

相关题目推荐

参考链接

• 题目原址：238. 除自身以外数组的乘积 - 力扣（LeetCode）

• 官方题解：除自身以外数组的乘积官方解法 - 力扣（LeetCode）