题目描述
给你一个整数数组 nums，返回数组 answer ，其中：
answer[i] = nums 中除 nums[i] 之外其余各元素的乘积
题目要求：
-
不能使用除法
-
时间复杂度需要是
O(n)
示例分析
示例 1
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
解释：
-
answer[0] = 2 * 3 * 4 = 24 -
answer[1] = 1 * 3 * 4 = 12 -
answer[2] = 1 * 2 * 4 = 8 -
answer[3] = 1 * 2 * 3 = 6
示例 2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
因为数组中有 0，所以不能简单地依赖总乘积去计算。
这也是题目要求“不能使用除法”的重要原因之一。
解题思路
这道题最关键的点有两个：
-
不能使用除法
-
要在线性时间内完成
很多同学第一次看到这题，最直接的想法可能是：
-
先求整个数组的乘积
total -
对于每个位置
i，答案就是total / nums[i]
但这种做法有两个问题：
1. 题目明确禁止使用除法
这条路直接被封死了。
2. 如果数组中有 0，会很麻烦
比如：
nums = [1,2,0,4]
整个乘积就是 0，根本没法通过除法直接恢复每个位置的答案。
所以这题必须换一种思路。
核心思想：前缀积 + 后缀积
对于某个位置 i，我们要求的是：
nums[0] * nums[1] * ... * nums[i-1] * nums[i+1] * ... * nums[n-1]
也就是说，它其实可以拆成两部分：
-
i左边所有数的乘积 -
i右边所有数的乘积
如果我们能快速知道这两个乘积，那么答案就很容易得到：
answer[i] = 左边乘积 × 右边乘积
这就是这道题最核心的思路。
你的代码在做什么
你给出的代码非常经典，而且做了空间优化：
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
if (len == 0) return new int[0];
int[] ans = new int[len];
ans[0] = 1;
int tmp = 1;
for (int i = 1; i < len; i++) {
ans[i] = ans[i - 1] * nums[i - 1];
}
for (int i = len - 2; i >= 0; i--) {
tmp *= nums[i + 1];
ans[i] *= tmp;
}
return ans;
}
}
它分成了两步：
-
第一遍从左往右，计算每个位置左边所有元素的乘积
-
第二遍从右往左，用变量
tmp维护右边所有元素的乘积，再乘到答案中
最终就得到了每个位置“除自己以外”的乘积。
第一步：先算前缀积
代码
ans[0] = 1;
for (int i = 1; i < len; i++) {
ans[i] = ans[i - 1] * nums[i - 1];
}
含义
这里的 ans[i] 在第一轮循环结束后，表示的是：
i左边所有元素的乘积
为什么 ans[0] = 1？
因为第 0 个位置左边没有任何元素。 空乘积按照惯例记为 1。
举个例子
假设：
nums = [1,2,3,4]
那么第一轮计算后：
-
ans[0] = 1 -
ans[1] = ans[0] * nums[0] = 1 * 1 = 1 -
ans[2] = ans[1] * nums[1] = 1 * 2 = 2 -
ans[3] = ans[2] * nums[2] = 2 * 3 = 6
所以这时：
ans = [1,1,2,6]
它表示的其实就是：
-
第 0 个位置左边乘积：
1 -
第 1 个位置左边乘积：
1 -
第 2 个位置左边乘积：
1*2=2 -
第 3 个位置左边乘积：
1*2*3=6
第二步：再乘上后缀积
代码
int tmp = 1;
for (int i = len - 2; i >= 0; i--) {
tmp *= nums[i + 1];
ans[i] *= tmp;
}
含义
这里用变量 tmp 来维护：
当前下标
i右边所有元素的乘积
然后把这个右边乘积乘到之前保存的左边乘积上：
ans[i] *= tmp;
于是最终：
ans[i] = 左边乘积 × 右边乘积
这正好就是题目要求的答案。
为什么 tmp 初始值是 1
因为最右边那个位置右边没有元素。
所以我们也把“空乘积”看作 1。
这样在从右往左更新时，逻辑会非常统一。
第二轮详细推演
还是看这个例子：
nums = [1,2,3,4]
第一轮之后：
ans = [1,1,2,6]
然后开始第二轮：
初始：
tmp = 1
i = 2
tmp *= nums[3] = 4
tmp = 4
ans[2] *= tmp
ans[2] = 2 * 4 = 8
i = 1
tmp *= nums[2] = 3
tmp = 12
ans[1] *= tmp
ans[1] = 1 * 12 = 12
i = 0
tmp *= nums[1] = 2
tmp = 24
ans[0] *= tmp
ans[0] = 1 * 24 = 24
最终：
ans = [24,12,8,6]
这就是答案。
为什么最后一个位置不用在第二轮里更新
注意你的循环是：
for (int i = len - 2; i >= 0; i--)
也就是说，从倒数第二个位置开始。
因为对于最后一个位置来说：
-
第一轮时，
ans[len - 1]已经是它左边所有元素的乘积 -
而它右边没有元素，乘积为
1
所以它本身已经是正确答案，不需要在第二轮里额外更新。
这也是代码写得很巧的地方。
代码逐段解析
1. 获取数组长度并处理空数组
int len = nums.length;
if (len == 0) return new int[0];
如果数组为空，直接返回空数组。
2. 定义答案数组
int[] ans = new int[len];
ans[0] = 1;
ans 用来存最终结果。 先把第一个位置设为 1，表示它左边没有元素。
3. 第一轮：存前缀积
for (int i = 1; i < len; i++) {
ans[i] = ans[i - 1] * nums[i - 1];
}
这一轮结束后，ans[i] 表示 i 左边所有元素的乘积。
4. 第二轮：乘上后缀积
int tmp = 1;
for (int i = len - 2; i >= 0; i--) {
tmp *= nums[i + 1];
ans[i] *= tmp;
}
tmp 动态维护从右往左的后缀积。
5. 返回答案
return ans;
为什么这题能做到 O(1) 额外空间
很多题解会说这题的空间复杂度是 O(1)（不算返回数组）。
这是因为：
-
ans是题目要求返回的结果数组，不算额外空间 -
除了
ans以外，只用了一个变量tmp
所以在题目的标准下，这种写法已经是空间优化版了。
如果你额外再开两个数组：
-
left[i]存左边乘积 -
right[i]存右边乘积
那虽然也能做出来，但空间复杂度会是 O(n)。
你这份代码比那种写法更进一步。
和“双数组写法”对比
双数组写法
思路是：
-
left[i]记录左边乘积 -
right[i]记录右边乘积 -
最后
ans[i] = left[i] * right[i]
优点：
-
非常直观
-
容易理解
缺点：
-
需要两个额外数组，空间复杂度是
O(n)
当前这种写法
思路是：
-
用
ans先存左边乘积 -
再用一个变量
tmp维护右边乘积并乘进去
优点：
-
时间复杂度
O(n) -
额外空间复杂度更低
-
代码更简洁
缺点：
-
第一次看时，不如双数组写法直观
复杂度分析
设数组长度为 n。
时间复杂度
O(n)
总共只遍历了两次数组。
空间复杂度
O(1)
不算返回数组 ans 的情况下，只使用了常数个额外变量。
如果把返回数组也算进去，那么是 O(n)。
总结
这道题的核心就在于把问题拆成两部分：
某个位置的答案 = 左边所有元素乘积 × 右边所有元素乘积
然后：
-
第一遍从左往右，把每个位置左边的乘积先存进
ans -
第二遍从右往左，用
tmpans上
所以你可以把这题记成一句话：
先存前缀积，再动态乘上后缀积。
这是一道非常经典的数组题，也是“前缀思想 + 空间优化”结合得非常漂亮的一题，值得彻底掌握。
