238. Product of Array Except Self

[namespace-io]

倒序

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

左右两边连续积，最后相乘

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size(); 
        vector<int> p(n, 1);
        vector<int> l(n + 2, 1);
        vector<int> r(n + 2, 1);
        for(int i = 1; i <= n; i++){
            l[i] = l[i-1] * nums[i-1];
            r[n+1-i] = r[n+2-i] * nums[n-i];
        }
        
        
        for(int i = 1; i <= n; i++){
            p[i-1] = l[i-1] * r[i+1];
        }
        
        return p;
    } 
};