每日一题(leetcode238):除自身以外数组的乘积--前缀和

不进阶是创建两个数组：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> left(n);
        vector<int> right(n);
        int mul=1;
        for(int i=0;i<n;i++){
            mul*=nums[i];
            left[i]=mul;
        }
        mul=1;
        for(int j=n-1;j>=0;j--){
            mul*=nums[j];
            right[j]=mul;
        }
        vector<int> ans(n);
        int pre=1;
        int las=1;
        for(int i=0;i<n;i++){
            pre= i-1<0? 1:left[i-1];
            las= i+1==n? 1:right[i+1];
            ans[i]=pre * las;
        }
        return ans;
    }
};

进阶是先将ans用作一个左乘积数组：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans(n);
        ans[0]=1;
        int mul=1;
        for(int i=1;i<n;i++){
            mul*=nums[i-1];
            ans[i]=mul;

        }
        int r=1;
        for(int j=n-1;j>=0;j--){
            ans[j]*=r;
            r*=nums[j];
        }
        return ans;
    }
};