描述

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

思路一

设置两个数组frombegin，fromend, 且设置frombegin[0] = 1,fromend[n-1] = 1, 按照如下公式frombegin[i] = nums[i-1]* frombegin[i-1], fromend[i] = nums[i+1] *fromend[i+1].

样例

可以看出，frombegin存的是前i个数的乘积（不包括i），fromend存的是i之后的乘积（不包括i），这样res = frombegin *fromend。这个需要的时间和空间

代码一

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        
        int n = nums.size();
        vector<int> frombegin(n);
        vector<int> fromend(n);
        frombegin[0] = 1;
        fromend[n-1] = 1;
        
        for(int i = 1; i<n;i++)
        {
            frombegin[i] = frombegin[i-1]*nums[i-1];
        }
        
        for(int i = n-2;i>=0;i--)
        {
            fromend[i] = fromend[i+1]*nums[i+1];
        }
        vector<int> res;
        for(int i = 0;i<n;i++)
        {
            res.push_back(frombegin[i]*fromend[i]);
        }
        
        return res;
    }
};

思路二

其实和思路一一样，不过我们可以在一个for循环里边完成

代码

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