238_ProductofArrayExceptSelf - a920604a/leetcode GitHub Wiki

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n= nums.size();
        vector<int> ret(n,1), left(n,1), right(n,1);
        //          1   2   3   4
        //left      1   1   2   6
        //right     24  12  4   1
        for(int i=1;i<n;++i) left[i] = left[i-1]*nums[i-1];
        for(int i=n-2;i>-1;i--) right[i] = right[i+1]*nums[i+1];
        
        for(int i=0;i<n;++i) ret[i] = left[i]*right[i];
        return ret;
        
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n,1), right(n,1);
        //  1   2   3   4   
        //l     1   2   6
        //r 24  12  4   
        //  
        for(int i=n-2;i>-1;i--) right[i] = right[i+1]*nums[i+1];
        int cur = 1;
        for(int i=1;i<n;++i){
            cur*=nums[i-1];
            right[i] *= cur;
        }
        return right;
    }
};