题目说明
给定整数数组 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)。
面试表达
先写出关系“当前位置答案 = 左侧乘积 × 右侧乘积”，再说明输出数组可复用为前缀积数组，后缀积只需一个滚动变量。这样能够同时满足 O(n) 时间、禁用除法和常数额外空间三个要求。