LeetCode 238. 除了自身以外数组的乘积
题目描述
题意分析
为每个下标
i求出除nums[i]之外所有元素的乘积。排除的是当前位置，其他位置即使与它的值相同，也仍然要参与相乘。题目要求不使用除法，并在 $O(n)$ 时间内完成；进阶要求只用 $O(1)$ 额外空间，返回数组不计入额外空间。数组允许包含零和负数，因此应直接组织需要相乘的元素，而不是先算总乘积再除去自身。
解法：前缀积 + 后缀积
核心思路
[!blue]
对位置
i来说，除自身以外的元素恰好分成两段：[0, i - 1]和[i + 1, n - 1]。因此答案等于「左侧全部元素的乘积」乘以「右侧全部元素的乘积」，两段没有遗漏，也不会包含自身。相邻位置的左侧区间只相差一个元素，可以从左向右不断累乘，不必为每个位置重新计算。右侧区间同理，只需改为从右向左。为了满足常数额外空间要求，直接把左侧乘积写进返回数组
res，右侧乘积则用一个滚动变量保存。第一趟从左向右：处理位置
i之前，left等于[0, i - 1]的乘积。先写入res[i] = left，保存不含自身的左侧乘积；再执行left *= nums[i]，使它成为下一个位置所需的左侧乘积。初始位置左边没有元素，空区间乘积取 $1$，所以从left = 1开始。第二趟从右向左：处理位置
i之前，right等于[i + 1, n - 1]的乘积，而res[i]已保存左侧乘积。先执行res[i] *= right，当前答案就完整了；再执行right *= nums[i]，为下一个向左访问的位置准备右侧乘积。最右侧的右边同样为空，因此初始化right = 1。两趟都遵循「先使用、后更新」，这正是排除自身的关键。遍历结束后，每个位置都已乘上完整的左右两段，返回
res即可。零和负数会自然参与这些乘法：只有一个零时，非零位置的答案都包含该零；有多个零时，每个答案都包含零，无需另设分支。
解题步骤
- 创建答案数组，初始化
left = 1。- 从左向右遍历：先令
res[i] = left，再执行left *= nums[i]。- 初始化
right = 1，从右向左遍历：先执行res[i] *= right，再执行right *= nums[i]。- 返回答案数组。
代码实现
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int left = 1;
for (int i = 0; i < n; i++) {
// 先写不含当前位置的左侧乘积，再把当前值计入累计量。
res[i] = left;
left *= nums[i];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
// 右侧也先使用后更新，保证当前位置不被乘进自己的答案。
res[i] *= right;
right *= nums[i];
}
return res;
}
}
func productExceptSelf(nums []int) []int {
n := len(nums)
res := make([]int, n)
left := 1
for i := 0; i < n; i++ {
// 先写不含当前位置的左侧乘积，再把当前值计入累计量。
res[i] = left
left *= nums[i]
}
right := 1
for i := n - 1; i >= 0; i-- {
// 右侧也先使用后更新，保证当前位置不被乘进自己的答案。
res[i] *= right
right *= nums[i]
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，进行两趟线性遍历。
- 空间复杂度：$O(1)$，按题意不计返回数组，额外只使用常数个变量；返回数组本身占 $O(n)$ 空间。
关键点总结
[!green]
- 将“除自身外”拆成互不重叠的左右两段，分别计算后相乘。
- 每次使用累计值时，它只包含已经遍历过的元素；当前元素要在本轮答案使用完后再乘入。
- 返回数组暂存左侧乘积，反向遍历补入右侧乘积，不需要另外建立两个辅助数组。
易错点总结
[!yellow]
- 用总乘积除以当前值：题目禁止除法，且遇到零会失效。
- 第一趟先执行
left *= nums[i]：会把自身乘入左侧乘积。- 第二趟先更新
right：同样会把自身重复乘入答案。- 将
left或right初始化为 $0$：空区间乘积应为乘法单位元 $1$，否则结果会全部归零。- 第二趟仍从左向右：无法在访问位置 $i$ 时得到其右侧区间的乘积。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 724. 寻找数组的中心下标 | 简单 | 同样把当前位置两侧拆成前缀与后缀，本题乘积排除自身，原题比较左右和。 |
| 42. 接雨水 | 困难 | 同样结合左右预处理信息，本题两侧相乘，原题由左右最高边界共同限制水位。 |