LeetCode 238. 除自身以外数组的乘积
题目核心
给定一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外所有元素的乘积。
要求：
- 不能使用除法。
- 时间复杂度为
O(n)。 - 空间复杂度为
O(1)（不包括输出数组）。
例如：
nums = [1, 2, 3, 4]
answer = [24, 12, 8, 6]解题思考过程
第一步：理解问题
计算每个元素除自身外所有元素的乘积。
第二步：暴力解法（嵌套循环）
最直接的思路：对每个元素，遍历其他所有元素计算乘积。
for i from 0 to n-1:
product = 1
for j from 0 to n-1:
if i != j:
product *= nums[j]
answer[i] = product
时间复杂度：O(n²)
空间复杂度：O(1)太慢了！需要 O(n) 时间。
第三步：想到除法（但题目禁止）
如果可以用除法：
total = 所有元素的乘积
answer[i] = total / nums[i]
时间复杂度：O(n)
空间复杂度：O(1)但题目禁止使用除法，原因：
- 数组可能包含0，除以0会出错
- 如果有多个0，结果应该都是0
第四步：想到前缀积和后缀积
不能用除法，那怎么计算除自身外的乘积？
除nums[i]外的乘积 = 前缀积[i] * 后缀积[i]
前缀积[i]：nums[0] * nums[1] * ... * nums[i-1]
后缀积[i]：nums[i+1] * nums[i+2] * ... * nums[n-1]示例：nums = [1, 2, 3, 4]
前缀积：[1, 1, 2, 6]
prefix[0] = 1（没有元素）
prefix[1] = 1
prefix[2] = 1 * 2 = 2
prefix[3] = 1 * 2 * 3 = 6
后缀积：[24, 12, 4, 1]
suffix[0] = 2 * 3 * 4 = 24
suffix[1] = 3 * 4 = 12
suffix[2] = 4
suffix[3] = 1（没有元素）
answer[i] = prefix[i] * suffix[i]
answer[0] = 1 * 24 = 24
answer[1] = 1 * 12 = 12
answer[2] = 2 * 4 = 8
answer[3] = 6 * 1 = 6第五步：空间优化
前缀积和后缀积需要两个数组，能不能只用一个数组？
可以！先计算前缀积存入结果数组，然后从右往左遍历，用变量记录后缀积：
1. 计算前缀积存入 answer
2. 初始化 r = 1（后缀积）
3. 从右往左遍历：
answer[i] = answer[i] * r
r *= nums[i]示例：nums = [1, 2, 3, 4]
第一步：前缀积
answer = [1, 1, 2, 6]
第二步：从右往左
i=3: answer[3] = 6 * 1 = 6, r = 1 * 4 = 4
i=2: answer[2] = 2 * 4 = 8, r = 4 * 3 = 12
i=1: answer[1] = 1 * 12 = 12, r = 12 * 2 = 24
i=0: answer[0] = 1 * 24 = 24, r = 24 * 1 = 24
最终：answer = [24, 12, 8, 6] ✓第六步：为什么这种方法能工作
时间复杂度：O(n) - 两次遍历
空间复杂度：O(1) - 不包括输出数组这是最优解法！
为什么不能用除法
题目明确禁止使用除法，原因有两个：
- 如果数组中包含
0，除法会出错。 - 除法的时间复杂度虽然也是
O(n)，但这不是题目期望考察的算法思想。
当前代码需要修正的地方
当前代码的核心思路是正确的：先用左侧乘积填充结果数组，再用右侧乘积乘以左侧乘积得到最终结果。
但是右侧遍历的条件有误：
for (let i = length - 1; i <= 0; i--) {这里的条件应该是 i >= 0，而不是 i <= 0。当前写法下循环只会在 i = length - 1 时检查一次，发现不满足条件就直接退出，右侧乘积完全没有被计算。
修正后的条件：
for (let i = length - 1; i >= 0; i--) {当前解法：左右两次遍历
先从左到右计算每个位置左侧所有元素的乘积：
var productExceptSelf = function (nums) {
let length = nums.length;
const res = new Array(length).fill(0);
res[0] = 1;
for (let i = 1; i < length; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
let r = 1;
for (let i = length - 1; i >= 0; i--) {
res[i] = res[i] * r;
r *= nums[i];
}
return res;
};算法思想
这道题的关键是：每个位置的答案等于它左侧所有元素的乘积，乘以它右侧所有元素的乘积。
第一步：计算左侧乘积
从左到右遍历，res[i] 表示 nums[i] 左侧所有元素的乘积。
nums = [1, 2, 3, 4]
res[0] = 1 // 第 0 个元素左侧没有元素
res[1] = res[0] * nums[0] = 1 * 1 = 1
res[2] = res[1] * nums[1] = 1 * 2 = 2
res[3] = res[2] * nums[2] = 2 * 3 = 6
此时 res = [1, 1, 2, 6]第二步：计算右侧乘积并合并
从右到左遍历，r 表示当前位置右侧所有元素的乘积。
r = 1 // 第 3 个元素右侧没有元素
res[3] = res[3] * r = 6 * 1 = 6, r = r * nums[3] = 1 * 4 = 4
res[2] = res[2] * r = 2 * 4 = 8, r = r * nums[2] = 4 * 3 = 12
res[1] = res[1] * r = 1 * 12 = 12, r = r * nums[1] = 12 * 2 = 24
res[0] = res[0] * r = 1 * 24 = 24, r = r * nums[0] = 24 * 1 = 24
最终 res = [24, 12, 8, 6]为什么能做到 O(1) 空间
输出数组 res 不计入空间复杂度。算法只用了一个额外变量 r 来记录右侧乘积，因此空间复杂度是 O(1)。
完整计算过程
以 nums = [2, 3, 4, 5] 为例：
第一步（左侧乘积）：
res[0] = 1
res[1] = 1 * 2 = 2
res[2] = 2 * 3 = 6
res[3] = 6 * 4 = 24
res = [1, 2, 6, 24]
第二步（右侧乘积）：
r = 1
res[3] = 24 * 1 = 24, r = 1 * 5 = 5
res[2] = 6 * 5 = 30, r = 5 * 4 = 20
res[1] = 2 * 20 = 40, r = 20 * 3 = 60
res[0] = 1 * 60 = 60, r = 60 * 2 = 120
最终 res = [60, 40, 30, 24]
验证：
60 = 3 * 4 * 5
40 = 2 * 4 * 5
30 = 2 * 3 * 5
24 = 2 * 3 * 4复杂度
- 时间复杂度：
O(n)，只遍历数组两次。 - 空间复杂度：
O(1)，除输出数组外只使用常数额外空间。
为什么循环顺序不能调换
左侧乘积必须从左到右计算，因为每个位置的左侧乘积依赖于前一个位置的左侧乘积。
右侧乘积必须从右到左计算，因为每个位置的右侧乘积依赖于后一个位置的右侧乘积。
如果调换顺序，无法正确传递乘积信息。
替代解法：使用两个数组
如果不要求 O(1) 空间，可以用两个数组分别存储左侧乘积和右侧乘积。
var productExceptSelf = function (nums) {
const n = nums.length;
const left = new Array(n).fill(1);
const right = new Array(n).fill(1);
const res = new Array(n);
for (let i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
for (let i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
for (let i = 0; i < n; i++) {
res[i] = left[i] * right[i];
}
return res;
};这种写法更直观，但空间复杂度是 O(n)。当前两次遍历的解法通过复用输出数组，将空间复杂度降到了 O(1)。
两种写法的关系
两个数组的写法是：
res[i] = left[i] * right[i]当前解法把 left 数组直接存到 res 里，然后边计算 right 边乘到 res 上：
res[i] = res[i] * r本质上是把三个循环合并成了两个循环，节省了一个数组的空间。
边界情况处理
数组长度为 1
题目约束 nums.length >= 2，所以不需要处理长度为 1 的情况。
包含 0 的情况
nums = [-1, 1, 0, -3, 3]
第一步：
res = [1, -1, -1, 0, 0]
第二步：
r = 1
res[4] = 0 * 1 = 0, r = 3
res[3] = 0 * 3 = 0, r = -9
res[2] = -1 * -9 = 9, r = 0
res[1] = -1 * 0 = 0, r = 0
res[0] = 1 * 0 = 0, r = 0
最终 res = [0, 0, 9, 0, 0]
验证：
0 = 1 * 0 * (-3) * 3
0 = (-1) * 0 * (-3) * 3
9 = (-1) * 1 * (-3) * 3
0 = (-1) * 1 * 0 * 3
0 = (-1) * 1 * 0 * (-3)算法正确处理了包含 0 的情况，因为没有使用除法，所以不会出现除零错误。