yicong@algo:~/code/05-array$ cat 0238-product-of-array-except-self.cpp
238. 除自身以外数组的乘积
// 思路
对每个位置 i,答案 = (i 左边所有数的乘积) × (i 右边所有数的乘积)。 所以只要把"左半前缀积"和"右半后缀积"分别算出来相乘即可,两趟扫描: 第一趟从左往右:ans[i] = nums[0] × nums[1] × ... × nums[i-1](不含 nums[i]) 第二趟从右往左:再把 nums[i+1] × ... × nums[n-1] 乘到 ans[i] 上 两趟都只用一个滚动变量 pre 记录"到目前为止的乘积",不需要额外数组。 ans 既当中间存储、又是最终返回值,所以除了 pre 之外没有额外空间。 为什么不用除法:题目明确要求"不要使用除法"。即使不限制,nums 里有 0 时 除法要单独统计 0 的个数,分情况讨论,反而更麻烦、更容易写错。
// 时间复杂度
O(n)。两趟各扫一遍,每个位置做 2 次乘法。
// 空间复杂度
O(1)。不计返回值 ans 的话只有 pre 一个变量。 题目把"返回的数组"排除在空间复杂度之外,所以这就是 O(1) 额外空间。
// 易错点
1. 别用除法。nums 里可能有 0,除法要额外统计 0 的个数并分情况处理。 2. ans 要开 n 个(vector<int> ans(l)),不是 n+1。 这点和 560 前缀和不同——560 里 sumnums 要 n+1 个是为了放哨兵 sumnums[0]=0, 这里每趟的 pre 初值就是 1,天然充当哨兵,不需要多开一格。 3. 两趟的 pre 都要重置为 1(第一趟用完是总乘积,不重置第二趟就全错了)。 4. 第二趟必须从右往左(i 递减)。写反就成了把左边又算一遍。 5. 第二趟里 ans[i] *= pre 要写在 pre *= nums[i] 之前。 顺序反了的话,pre 里已经包含 nums[i] 自己,答案会把自身乘进去。 6. 用 int 就够:题目保证任意元素的前缀积、后缀积(甚至整个数组的乘积) 都在 32 位整数范围内,不用 long long。
// 面试口述要点
1. 先给暴力:每个位置都重新扫一遍其余元素,O(n²); 2. 再给除法解:先求总乘积,ans[i] = 总积 / nums[i],O(n); 但要处理 0(没有 0 / 一个 0 / 两个以上 0),而且题目不允许用除法; 3. 正解两趟扫描:位置 i 的答案 = 左半乘积 × 右半乘积; 第一趟把左半乘积写进 ans,第二趟滚动维护右半乘积乘上去; 4. 强调空间为什么是 O(1):ans 被复用成输出数组,额外的只有一个滚动变量。 这是这道题"进阶要求"的落脚点,也是它比 560 高明的地方。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int l = (int)nums.size();
vector<int> ans(l);
// ---------- 第一趟:从左往右,ans[i] 先放"左半乘积" ----------
// ans[i] = nums[0] × ... × nums[i-1],不含 nums[i] 自己
int pre = 1;
for (int i=0; i<l; i++) {
ans[i] = pre; // 先写入左半乘积
pre *= nums[i]; // 再把自己乘进去,留给下一个位置用
}
// ---------- 第二趟:从右往左,把"右半乘积"乘上去 ----------
// ans[i] *= nums[i+1] × ... × nums[n-1]
pre = 1; // 必须重置
for (int i=l-1; i>=0; i--){
ans[i] *= pre; // 先乘右半乘积
pre *= nums[i]; // 再把自己乘进去,留给左边位置用
}
return ans;
}
};
// 本地测试:输入 n,然后 n 个整数;输出每个位置除自身以外其余元素的乘积
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<int> nums(n);
for (int& x : nums) cin >> x;
vector<int> ans = Solution().productExceptSelf(nums);
if (ans.empty()) {
cout << "none\n";
} else {
for (size_t i = 0; i < ans.size(); ++i)
cout << ans[i] << (i + 1 == ans.size() ? '\n' : ' ');
}
return 0;
}