leetcode：238. Product of arrays other than itself

Title source

• leetcode：238. The product of an array other than itself

title

The prefix and

According to the meaning , For each $ans[i]$ Both consist of two parts ：
$$(nums[0]\times nums[1]\times ...\times nums[i-1])\times (nums[i+1]\times nums[i+2]\times ...\times nums[n-1])$$

therefore , We can use the idea of prefix and , Request two arrays $s1[?],s2[?]$ （ hypothesis n = nums.size()）

• $s1[i]=num[0.....i-1]$
• $s2[i]=num[i+1....n-1]$

After processing ： $ans[i]=s1[i]\ast s2[i]$

class Solution {
    
public:
    vector<int> productExceptSelf(vector<int>& nums) {
    
        if(nums.empty()){
    
            return {
    };
        }

        int m = nums.size();

       
        std::vector<int> s1(m, 0), s2(m, 0);
        
        // s1[i]  Index  i  The product of all the elements on the left 
        s1[0] = 1;
        for (int i = 1; i < m; ++i) {
    
            s1[i] = s1[i - 1] * nums[i - 1];
        }

        // s2[i]  Index  i  The product of all elements on the right 
        s2[m - 1] = 1;
        for (int i = m - 2; i >= 0; --i) {
    
            s2[i] = s2[i + 1] * nums[i + 1];
        }

        //  For index  i, except  nums[i]  The product of other elements is the product of all elements on the left multiplied by the product of all elements on the right 
        vector<int> ans(m, 0);
        for (int i = 0; i < m; ++i) {
    
            ans[i] = s1[i] * s2[i];
        }
        return ans;
    }
};

Spatial complexity O(1)O(1) Methods

Because the output array is not included in the space complexity , Then we can L or R Arrays are computed using output arrays . First treat the output array as L Array to calculate , And then dynamically construct R Array gets the result .

class Solution {
    
public:
    vector<int> productExceptSelf(vector<int>& nums) {
    
        if(nums.empty()){
    
            return {
    };
        }

        int m = nums.size();
        int pre = 0, front = 0;
       
        vector<int> ans(m, 1);

        pre = 1;
        ans[0] *= pre;
        for (int i = 1; i < m; ++i) {
    
            pre = pre * nums[i - 1];
            ans[i] *= pre;
        }
        

        front = 1;
        ans[m - 1] *= front;
        for (int i = m - 2; i >= 0; --i) {
    
            front = front * nums[i + 1];
            ans[i] *= front;
        }

        
        return ans;
    }
};