238. 除自身以外数组的乘积
题目描述
输入一个整数数组 nums。
返回一个同样长度的数组 answer，其中 answer[i] 等于 nums 里除去 nums[i] 之后，其余所有元素相乘的结果。
不允许使用除法，并且算法的时间复杂度要求为 O(n)。
题目保证任意前缀或后缀的乘积都能用 32 位整数表示。
示例 1
输入：nums = [1,2,3,4] 输出：[24,12,8,6]
解释：例如 answer[0] = 2*3*4 = 24，answer[3] = 1*2*3 = 6。
示例 2
输入：nums = [-1,1,0,-3,3] 输出：[0,0,9,0,0]
解释：只有 answer[2] 不包含 0，等于 (-1)*1*(-3)*3 = 9，其余位置都乘到了 0。
数据范围
2 <= nums.length <= 10^5-30 <= nums[i] <= 30- 每个
answer[i]都在 32 位整数范围内。
进阶：能否只用 O(1) 的额外空间？分析空间时，返回的数组不计入。
解题思路：两遍扫描前后缀积
第一次从左到右把左侧乘积写入 answer；第二次从右到左维护右侧乘积并乘入 answer。
为什么正确
第二次扫描到 i 时，answer[i] 已是所有左侧元素乘积，right 是所有右侧元素乘积。
复杂度分析
时间 O(n)，额外空间 O(1)（不计输出）。
易错点
使用总乘积除以 nums[i] 会被零破坏，也违反禁用除法的要求。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def productExceptSelf(self, nums):
ans=[1]*len(nums); left=1
for i,x in enumerate(nums): ans[i]=left; left*=x
right=1
for i in range(len(nums)-1,-1,-1): ans[i]*=right; right*=nums[i]
return ansclass Solution {
public int[] productExceptSelf(int[] nums) {
int[] ans = new int[nums.length];
int left = 1;
for (int i = 0; i < nums.length; i++) {
ans[i] = left;
left *= nums[i];
}
int right = 1;
for (int i = nums.length - 1; i >= 0; i--) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
}class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> ans(nums.size(), 1);
int left = 1;
for (int i = 0; i < (int)nums.size(); i++) {
ans[i] = left;
left *= nums[i];
}
int right = 1;
for (int i = (int)nums.size() - 1; i >= 0; i--) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
};func productExceptSelf(nums []int) []int {
ans := make([]int, len(nums))
left := 1
for i, x := range nums {
ans[i] = left
left *= x
}
right := 1
for i := len(nums) - 1; i >= 0; i-- {
ans[i] *= right
right *= nums[i]
}
return ans
}var productExceptSelf = function(nums) {
const ans = new Array(nums.length).fill(1);
let left = 1;
for (let i = 0; i < nums.length; i++) {
ans[i] = left;
left *= nums[i];
}
let right = 1;
for (let i = nums.length - 1; i >= 0; i--) {
ans[i] *= right;
right *= nums[i];
}
return ans;
};function productExceptSelf(nums: number[]): number[] {
const ans: number[] = new Array(nums.length).fill(1);
let left = 1;
for (let i = 0; i < nums.length; i++) {
ans[i] = left;
left *= nums[i];
}
let right = 1;
for (let i = nums.length - 1; i >= 0; i--) {
ans[i] *= right;
right *= nums[i];
}
return ans;
};其他解法
左右乘积数组直接存下前缀积和后缀积；主解法把前缀积写进答案数组、后缀积用一个变量维护，把额外空间压到 O(1)。
解法 2：左右乘积数组 时间 O(n)，空间 O(n)
L[i] 表示 nums[i] 左侧所有元素的乘积，R[i] 表示右侧所有元素的乘积。从左到右算出 L，从右到左算出 R。答案 answer[i] = L[i] × R[i]。
两个辅助数组各自含义清楚，最容易理解。多用 O(n) 空间，不满足进阶的常数空间要求。
class Solution:
def productExceptSelf(self, nums):
n = len(nums)
L, R = [1] * n, [1] * n
for i in range(1, n):
L[i] = L[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
R[i] = R[i + 1] * nums[i + 1]
return [L[i] * R[i] for i in range(n)]class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] L = new int[n], R = new int[n], ans = new int[n];
L[0] = 1;
for (int i = 1; i < n; i++) L[i] = L[i - 1] * nums[i - 1];
R[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) R[i] = R[i + 1] * nums[i + 1];
for (int i = 0; i < n; i++) ans[i] = L[i] * R[i];
return ans;
}
}class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> L(n, 1), R(n, 1), ans(n);
for (int i = 1; i < n; i++) L[i] = L[i - 1] * nums[i - 1];
for (int i = n - 2; i >= 0; i--) R[i] = R[i + 1] * nums[i + 1];
for (int i = 0; i < n; i++) ans[i] = L[i] * R[i];
return ans;
}
};func productExceptSelf(nums []int) []int {
n := len(nums)
L, R, ans := make([]int, n), make([]int, n), make([]int, n)
L[0] = 1
for i := 1; i < n; i++ {
L[i] = L[i-1] * nums[i-1]
}
R[n-1] = 1
for i := n - 2; i >= 0; i-- {
R[i] = R[i+1] * nums[i+1]
}
for i := 0; i < n; i++ {
ans[i] = L[i] * R[i]
}
return ans
}var productExceptSelf = function(nums) {
const n = nums.length;
const L = new Array(n).fill(1), R = new Array(n).fill(1);
for (let i = 1; i < n; i++) L[i] = L[i - 1] * nums[i - 1];
for (let i = n - 2; i >= 0; i--) R[i] = R[i + 1] * nums[i + 1];
return L.map((v, i) => v * R[i]);
};function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const L: number[] = new Array(n).fill(1), R: number[] = new Array(n).fill(1);
for (let i = 1; i < n; i++) L[i] = L[i - 1] * nums[i - 1];
for (let i = n - 2; i >= 0; i--) R[i] = R[i + 1] * nums[i + 1];
return L.map((v, i) => v * R[i]);
}