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

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

news 2026/8/5 1:28:29

题目说明

给定整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余元素的乘积。

要求：

时间复杂度为 O(n)；
不能使用除法；
进阶要求除输出数组外只使用 O(1) 额外空间。

例如：

输入：nums = [1,2,3,4]
输出：[24,12,8,6]

思路：答案等于左侧乘积乘右侧乘积

对于每个位置 i，把除自身以外的元素拆成左右两部分：

answer[i] = nums[0] * ... * nums[i-1] * nums[i+1] * ... * nums[n-1]

也就是：

answer[i] = 左侧所有元素的乘积 * 右侧所有元素的乘积

第一次从左向右遍历，让 answer[i] 保存 nums[i] 左侧所有元素的乘积。第二次从右向左遍历，用变量 right 累积右侧乘积，并将它乘进 answer[i]。

以 [1,2,3,4] 为例：

左侧前缀积写入 answer：[1,1,2,6]
从右向左累乘后缀积：[24,12,8,6]

answer[0] 左侧没有元素，空乘积记为 1；最后一个元素右侧同理。

Python 代码

class Solution:def productExceptSelf(self, nums: list[int]) -> list[int]:n = len(nums)answer = [1] * nleft = 1for i in range(n):answer[i] = leftleft *= nums[i]right = 1for i in range(n - 1, -1, -1):answer[i] *= rightright *= nums[i]return answer

还可以省去单独的 left 变量，直接利用已经写入的答案数组：

class Solution:def productExceptSelf(self, nums: list[int]) -> list[int]:n = len(nums)answer = [1] * nfor i in range(1, n):answer[i] = answer[i - 1] * nums[i - 1]right = 1for i in range(n - 1, -1, -1):answer[i] *= rightright *= nums[i]return answer

正确性说明

第一次遍历结束后，answer[i] 等于 nums[i] 左侧全部元素的乘积。第二次遍历到位置 i 时，变量 right 等于 nums[i] 右侧全部元素的乘积。二者相乘后，answer[i] 正好包含除 nums[i] 以外的所有元素，因此算法得到正确答案。

为什么不使用除法

直接计算数组总乘积再除以当前元素，不仅违反题目要求，还需要额外处理零：

一个零时，只有零所在位置可能得到非零答案；
两个及以上零时，所有答案都是零。

前缀积与后缀积不依赖除法，因此不需要针对零编写特殊分支，负数也能自然处理。

复杂度分析

时间复杂度：O(n)。数组被线性遍历两次。
空间复杂度：O(1) 额外空间。返回数组不计入额外空间时，只使用常数个变量。

易错点

answer 的初始值必须是 1，不能是 0。
更新 right 的顺序不能颠倒：先执行 answer[i] *= right，再执行 right *= nums[i]，否则会把当前元素乘入答案。
不需要单独处理零。
不要把两个完整的前缀积、后缀积数组都保留下来，否则额外空间会变成 O(n)。