除了自身以外数组的乘积
Product of Array Except Self
返回一个新数组，其中每个位置的值是原数组中除该位置外所有元素的乘积，且不能使用除法。
在力扣中练习题目描述
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums =[1,2,3,4]输出:[24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 输入 保证 数组
answer[i]在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
解题思路
主解法
左右乘积 · 两趟扫描
每个位置 = 左边所有数之积 × 右边所有数之积
如果数组里没有 0，最直接的做法是算出总乘积，再除以每个数。但题目禁止除法，而且有 0 时除法会失效。
换成乘法：位置 i 的答案 = 左边所有数之积 × 右边所有数之积。
先用 result 数组存左侧乘积：result[i] = result[i-1] * nums[i-1]。然后从右往左维护一个 suffix，表示 i 右侧所有数的乘积，把它乘进 result[i]，再更新 suffix *= nums[i]。
自拟主例 [2,4,3,5]：左趟得到 [1,2,8,24]；右趟从 5 开始往前乘，最终得到 [60,30,40,24]。
分步图解
result[1] = result[0] × nums[0] = 2。
- i
- 1
分步图解
result[3] 再乘右侧乘积 1，得到 24；右侧乘积更新为 5。
- suffix
- 1
- result[i]
- 24
时间 O(n)，除输出数组外只用了常数空间。
时间 O(n)空间 O(1)（不计输出）
易错点
- 用总乘积除以 nums[i]：题目禁止除法，且数组含 0 时会出错。
- 右趟先更新 suffix 再乘 result：当前位置会把自己的值也算进去。
- result 初始化为 0：左趟所有乘积都会变成 0。
- 把输出数组算进额外空间：题目通常不把返回数组计入空间复杂度。
代码与演示
演示输入
nums = [2,4,3,5]result 全部初始化为 1；先从左往右存“左边所有数的乘积”。
- n
- 4
查看 C++ 代码
延伸阅读
- “前缀积 × 后缀积”与“前缀和 + 哈希表”是同一类拆解：把区间统计量拆成左右两部分。
- 如果题目要求 O(1) 额外空间且输出数组不算，当前写法已经满足；如果连输出都不能用，需要更复杂的原地编码。