leetcode238. 除自身以外数组的乘积

题目

题解

使用前缀积，首先分别从左到右、从右到左记录下每个元素的积，要求第i个元素除自身以外数组的乘积，只需要该该元素i-1个从左到右的乘积*(i+1)个从右到左的乘积。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int>lpro(nums.size() + 1, 1),rpro(nums.size() + 1, 1), ans;
        for(int i = 0, j = nums.size() ; i < nums.size() && j > 0; i++,j--){
            lpro[i+1] = nums[i] * lpro[i]; 
            rpro[j-1] = nums[j-1] * rpro[j];
        }
        for(int i = 0; i < nums.size() ; i++){
            ans.push_back(lpro[i]*rpro[i+1]);
        }
        return ans;
    }
};