Leetcode-238. product of arrays other than itself

Mathematical problems

---

Topic details

Give you an array of integers nums, return Array answer , among answer[i] be equal to nums Middle Division nums[i] Product of other elements .
Subject data Guarantee Array nums The product of all prefix elements and suffixes of any element in 32 position In the range of integers .
Please do not use division , And in O(n) Complete this question in time complexity .

---

Example 1：

 Input : nums = [1,2,3,4]
 Output : [24,12,8,6]

Example 2:

 Input : nums = [-1,1,0,-3,3]
 Output : [0,0,9,0,0]

Ideas :
Like a brain teaser , The product of each number in the array other than itself is the left multiplied by the right
And how to get the left / The product of all numbers on the right ?
Similar to dynamic programming , We traverse once from left to right , use left Remember the number traversed nums[i] Left product of
namely nums[0]*nums[1]...*nums[i-1]
And it res[i] Multiply and update left Until all the nums[i] Get the corresponding res[i]
( At this time, all the left products are obtained through traversal )
Then use the same method to traverse from right to left , utilize right memory , It's the same thing
Finally, after traversing both sides, we get the desired result
( Note initialization left and right All are 1)

My code ：

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

    }
};

We can also combine the two loops into one , To get the following code :

class Solution 
{
    
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
    
        int n = nums.size();
        int left = 1, right = 1;
        vector<int> res(n, 1);

        for (int i = 0; i < n; ++i)
        {
    
            res[i] *= left;
            left *= nums[i];

            res[n-1-i] *= right;
            right *= nums[n-1-i];
        }
        return res;

    }
};