LeetCode 238. 除自身以外数组的乘积：前缀积 + 后缀积详解
1. 这道题属于什么算法思想
这题主要归类为：
数组 / 前缀积 + 后缀积它和“前缀和”思想类似，但这里做的不是加法，而是乘法。
题目中每个位置的答案，都由两部分组成：
当前位置左边所有元素的乘积。 当前位置右边所有元素的乘积。把这两部分相乘，就得到“除自身以外数组的乘积”。
2. 这道题到底在问什么
题目要求返回数组answer，满足：
answer[i] 等于 nums 中除了 nums[i] 之外其余所有元素的乘积。例如：
nums = [1, 2, 3, 4]结果是：
answer[0] = 2 * 3 * 4 = 24 answer[1] = 1 * 3 * 4 = 12 answer[2] = 1 * 2 * 4 = 8 answer[3] = 1 * 2 * 3 = 6因此：
answer = [24, 12, 8, 6]题目还有两个限制：
1. 不允许使用除法。 2. 要在 O(n) 时间内完成。3. 为什么不能直接用总乘积除自身
最直观的想法是先计算所有元素的总乘积：
total = nums[0] * nums[1] * ... * nums[n - 1]然后：
answer[i] = total / nums[i]但题目明确禁止使用除法。
而且数组中可能有0。
例如：
nums = [1, 2, 0, 4]总乘积是：
0如果计算answer[2]，会得到：
0 / 0这无法计算。
因此要换一种不依赖除法的方法。
4. 为什么不直接使用暴力解法
可以直接使用暴力解法，它是正确的。
思路是：对于每个下标i，重新遍历整个数组，跳过nums[i]，把其余元素相乘。
classSolution{publicint[]productExceptSelf(int[]nums){intn=nums.length;int[]answer=newint[n];for(inti=0;i<n;i++){intproduct=1;for(intj=0;j<n;j++){// 当前答案不能乘 nums[i] 自己。if(i!=j){product*=nums[j];}}answer[i]=product;}returnanswer;}}例如：
nums = [1, 2, 3, 4]计算answer[0]时，需要计算：
2 * 3 * 4计算answer[1]时，又需要计算：
1 * 3 * 4其中：
3 * 4这部分被重复计算了。随着数组变大，左边和右边的很多乘积都会反复计算。
时间复杂度是：
外层循环 n 次。 每次内层循环遍历 n 次。 总时间复杂度是 O(n^2)。题目明确要求在O(n)时间内完成，因此暴力法不能作为最终提交解法。
前缀积和后缀积的作用，就是提前保存并复用这些重复乘积：
left[i] 保存 i 左边所有元素的乘积。 right[i] 保存 i 右边所有元素的乘积。于是每个答案只需：
answer[i] = left[i] * right[i]不再需要为每个i重新扫描整个数组。
5. 第一性原理：每个答案由左边和右边组成
对于nums[i]，需要排除的只有它自己。
数组中其余元素可以自然拆成两部分：
nums[i] 左边的元素。 nums[i] 右边的元素。因此：
answer[i] = 左边所有元素的乘积 * 右边所有元素的乘积例如：
nums = [1, 2, 3, 4] 下标: 0 1 2 3对于：
i = 2，nums[2] = 3左边元素是：
1, 2右边元素是：
4所以：
answer[2] = (1 * 2) * 4 = 8这就是整题核心：
每个位置不需要重新遍历整个数组，只需要知道它左边的乘积和右边的乘积。6. 用 left 和 right 两个数组直接表达思路
定义：
left[i]：nums[i] 左边所有元素的乘积。 right[i]：nums[i] 右边所有元素的乘积。那么：
answer[i] = left[i] * right[i]对于：
nums = [1, 2, 3, 4]6.1 left 数组
left[0]表示nums[0]左边所有元素的乘积。
nums[0]左边没有元素，因此：
left[0] = 1为什么是1而不是0？
因为乘法中的空乘积定义为1。
它的作用是保证：
没有左边元素时，answer[0] 只由右边元素决定。 1 * 右边乘积 = 右边乘积。之后从左到右计算：
left[1] = nums[0] = 1 left[2] = nums[0] * nums[1] = 1 * 2 = 2 left[3] = nums[0] * nums[1] * nums[2] = 1 * 2 * 3 = 6所以：
left = [1, 1, 2, 6]递推关系是：
left[i] = left[i - 1] * nums[i - 1]原因是：
nums[i] 左边的元素 = nums[i - 1] 左边的元素，再加上 nums[i - 1] 自己。6.2 right 数组
right[3]表示nums[3]右边所有元素的乘积。
nums[3]右边没有元素，因此：
right[3] = 1之后从右到左计算：
right[2] = nums[3] = 4 right[1] = nums[2] * nums[3] = 3 * 4 = 12 right[0] = nums[1] * nums[2] * nums[3] = 2 * 3 * 4 = 24所以：
right = [24, 12, 4, 1]递推关系是：
right[i] = right[i + 1] * nums[i + 1]原因是：
nums[i] 右边的元素 = nums[i + 1] 右边的元素，再加上 nums[i + 1] 自己。6.3 合并 left 和 right
最后逐个位置相乘：
answer[0] = left[0] * right[0] = 1 * 24 = 24 answer[1] = left[1] * right[1] = 1 * 12 = 12 answer[2] = left[2] * right[2] = 2 * 4 = 8 answer[3] = left[3] * right[3] = 6 * 1 = 6因此：
answer = [24, 12, 8, 6]7. 用表格完整推导
对于：
nums = [1, 2, 3, 4]| i | nums[i] | left[i]：左边乘积 | right[i]：右边乘积 | answer[i] |
|---|---|---|---|---|
| 0 | 1 | 1 | 24 | 24 |
| 1 | 2 | 1 | 12 | 12 |
| 2 | 3 | 2 | 4 | 8 |
| 3 | 4 | 6 | 1 | 6 |
表格中每一行都满足：
answer[i] = left[i] * right[i]8. 数组中有 0 时为什么仍然正确
前缀积和后缀积不使用除法，因此能自然处理0。
例如：
nums = [1, 2, 0, 4]正确答案应为：
answer = [0, 0, 8, 0]解释：
answer[0] = 2 * 0 * 4 = 0 answer[1] = 1 * 0 * 4 = 0 answer[2] = 1 * 2 * 4 = 8 answer[3] = 1 * 2 * 0 = 0计算数组：
left = [1, 1, 2, 0] right = [0, 0, 4, 1]相乘：
[1 * 0, 1 * 0, 2 * 4, 0 * 1] = [0, 0, 8, 0]结果正确。
如果有两个或更多个0，每个位置除自身外仍至少包含一个0，所以所有答案都是0。前缀积和后缀积同样会自然得到这个结果。
9. Java 代码完整注释
classSolution{publicint[]productExceptSelf(int[]nums){intn=nums.length;// left[i] 表示 nums[i] 左边所有元素的乘积。int[]left=newint[n];// right[i] 表示 nums[i] 右边所有元素的乘积。int[]right=newint[n];// answer[i] = left[i] * right[i]。int[]answer=newint[n];// nums[0] 左边没有元素，空乘积为 1。left[0]=1;// 从左到右计算每个位置左边的乘积。for(inti=1;i<n;i++){// nums[i] 左边的乘积// = nums[i - 1] 左边的乘积 * nums[i - 1]。left[i]=left[i-1]*nums[i-1];}// nums[n - 1] 右边没有元素，空乘积为 1。right[n-1]=1;// 从右到左计算每个位置右边的乘积。for(inti=n-2;i>=0;i--){// nums[i] 右边的乘积// = nums[i + 1] 右边的乘积 * nums[i + 1]。right[i]=right[i+1]*nums[i+1];}// 左边乘积 * 右边乘积，就是除 nums[i] 之外所有元素的乘积。for(inti=0;i<n;i++){answer[i]=left[i]*right[i];}returnanswer;}}10. 复杂度分析
时间复杂度：
O(n)分别计算left、right和answer，每一轮都只遍历数组一次，总体仍是线性时间。
空间复杂度：
O(n)除了题目要求返回的answer外，还使用了left和right两个长度为n的数组。
后续可以把left和right的信息复用到answer和一个普通变量中，从而优化额外空间；但这属于空间优化，不是理解本题的必要前提。
11. 总结
这题属于：
数组 / 前缀积 + 后缀积核心公式是：
answer[i] = left[i] * right[i]其中：
left[i] 表示 nums[i] 左边所有元素的乘积。 right[i] 表示 nums[i] 右边所有元素的乘积。left[0]和right[n - 1]都初始化为1，因为两侧没有元素时，空乘积应该是不改变结果的乘法单位元1。
可以把整题记成一句话：
每个位置的答案，等于它左边所有数的乘积乘以它右边所有数的乘积。
