【算法面试必刷】238. 除了自身以外数组的乘积
目录
题目
题目链接
思路
复杂度
代码1（不使用除法）
代码2（使用除法）
题目
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
题目链接
238. 除了自身以外数组的乘积 - 力扣（LeetCode）
https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked
思路
核心思想：前后缀乘积分解
对于任意位置 i，我们希望得到：
result[i] = nums[0] × nums[1] × ... × nums[i-1] // 左边所有数的乘积
× nums[i+1] × ... × nums[n-1] // 右边所有数的乘积
两阶段计算法：
阶段1：计算左边乘积（从左到右遍历）
初始化：result[0] = 1（第一个元素左边没有元素） 递推公式：result[i] = result[i-1] × nums[i-1] 示例：nums = [1, 2, 3, 4] result 第一阶段： result[0] = 1 result[1] = result[0] × nums[0] = 1 × 1 = 1 result[2] = result[1] × nums[1] = 1 × 2 = 2 result[3] = result[2] × nums[2] = 2 × 3 = 6 result = [1, 1, 2, 6] ← 这是左边乘积
阶段2：计算右边乘积并合并（从右到左遍历）
使用变量 suffixProduct 记录右边乘积 从右向左遍历： 当前结果 result[i] = result[i] × suffixProduct 更新 suffixProduct = suffixProduct × nums[i] 继续示例： 初始化：suffixProduct = 1 i=3: result[3] = 6 × 1 = 6, suffixProduct = 1 × 4 = 4 i=2: result[2] = 2 × 4 = 8, suffixProduct = 4 × 3 = 12 i=1: result[1] = 1 × 12 = 12, suffixProduct = 12 × 2 = 24 i=0: result[0] = 1 × 24 = 24, suffixProduct = 24 × 1 = 24 result = [24, 12, 8, 6] ← 最终结果
复杂度
时间复杂度：O(n)
空间复杂度：O(1)（输出数组不计入）
代码1（不使用除法）
class Solution {
public:
vector productExceptSelf(vector& nums) {
// 获取数组长度
int size = nums.size();
// 边界情况：空数组直接返回空结果
if (size == 0) {
return {};
}
// 初始化结果数组，所有元素初始为1
vector result(size, 1);
// 第一阶段：计算每个元素左边所有元素的乘积（前缀积）
// result[i] 存储 nums[0] × nums[1] × ... × nums[i-1]
for (int i = 1; i < size; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
// 第二阶段：计算每个元素右边所有元素的乘积（后缀积）
// 并用右边乘积乘以左边乘积得到最终结果
int suffixProduct = 1; // 从右向左累乘的后缀积
for (int i = size - 1; i >= 0; i--) {
// 当前结果 = 左边乘积 × 右边乘积
result[i] *= suffixProduct;
// 更新后缀积，包含当前元素
suffixProduct *= nums[i];
}
return result;
}
}; 代码2（使用除法）
class Solution {
public:
vector productExceptSelf(vector& nums) {
vector ans; // 结果数组
int sum = 1, tmp = 1; // sum: 所有数的乘积，tmp: 所有非零数的乘积
int cnt = 0; // 统计0的个数
// 1. 统计0的个数
for (auto i : nums) {
if (!i) cnt++; // 如果i==0，cnt加1
}
// 2. 如果有两个或更多的0，所有结果都是0
if (cnt >= 2) {
for (int i = 0; i < nums.size(); i++) {
ans.push_back(0); // 全部填充0
}
return ans;
}
// 3. 计算所有数的乘积（可能为0）
for (auto i : nums) {
sum *= i; // 注意：如果数组中有0，sum会是0
}
// 4. 计算所有非零数的乘积
for (auto i : nums) {
if (i) { // 如果i不为0
tmp *= i;
}
}
// 5. 计算结果
for (auto i : nums) {
if (i) {
// 如果当前元素不为0，用总乘积除以当前元素
ans.push_back(sum / i);
} else {
// 如果当前元素为0，结果是所有非零数的乘积
ans.push_back(tmp);
}
}
return ans;
}
};
