238. 除了自身以外数组的乘积
3 min
题目
解法：前后缀积
思路
核心思想是利用前缀积和后缀积：每个位置的乘积等于其左侧所有元素的乘积乘右侧所有元素的乘积。
正确性证明：对于任意位置i，左侧乘积是前i-1个元素的累积（ans[i-1]），右侧乘积是从i+1到末尾的累积（now变量）。由于题目保证乘积在32位整数范围内，且两次遍历分别计算前缀和后缀，不会遗漏或重复计算。移动指针时，now动态更新后缀积，确保每个位置都能O(1)获取左右两侧乘积。
- Step 1: 初始化ans[0]为nums[0]
- Step 2: 从左到右遍历，ans[i]存储nums[0]到nums[i]的前缀积
- Step 3: 初始化now=1记录后缀积
- Step 4: 从右到左遍历，ans[i]更新为ans[i-1]（左积）* now（右积）
- Step 5: 更新now *= nums[i]为下一位置准备
复杂度
- 时间复杂度: ，两次线性遍历，无嵌套循环。
- 空间复杂度: ，除输出数组外仅用常数变量（now）。
代码
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> ans(nums.size());
ans[0] = nums[0];
for(int i = 1;i<nums.size();i++){
ans[i] = ans[i-1]*nums[i];
}
int now = 1;
for(int i = nums.size()-1;i>=0;i--){
if(i==0){
ans[i] = now;
}
else{
ans[i] = ans[i-1]*now;
}
now *= nums[i];
}
return ans;
}
};