LeetCode 238 Product of Array Except Self
概述
https://leetcode.com/problems/product-of-array-except-self/
要求 O(n) 时间复杂度，不能用除法。
这不是剑指 Offer 上的原题么。
前缀积与后缀积
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> lp = nums, rp = nums;
for (int i = 1; i < nums.size(); i ++) {
lp[i] = lp[i-1] * nums[i];
}
for (int i = nums.size() - 2; i >= 0; i --) {
rp[i] = rp[i+1] * nums[i];
}
vector<int> ans = nums;
ans[0] = rp[1];
ans[ans.size()-1] = lp[ans.size()-2];
for (int i = 1; i < ans.size() - 1; i ++) {
ans[i] = lp[i-1] * rp[i+1];
}
return ans;
}
};