Product of Array Except Self

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

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

这道题显然不能用总乘积来除以相应的数，因为会有0出现。

一般的方法是分别用两个数组，一个数组从前往后记录数组的乘积，一个数组从后往前记录数组的乘积

例如对于数组nums    [1, 2, 3, 4, 5]
fromBegin[i]记录从0到i-1的乘积     fromBegin[0] = 1
fromBegin         [1，1，2，6，24]
fromEnd[i]记录从n-i到n-1的乘积     fromEnd[0] = 1
fromEnd        [120, 60, 20, 5, 1] 

res            [120, 60, 40,30,24]
那么  res[i] = fromBegin[i] * fromEnd[n - i - 1]

代码为:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int l = nums.size();
        /*fromBegin[i]记录[0, i -1]的乘积，fromBegin[0] = 1;
         *fromEnd[i]记录从[n - i,n-1]的乘积，fromEnd[n - 1] = 1
         */
        vector<int> fromBegin(l, 1);
        vector<int> fromEnd(l, 1);
        vector<int> res(l);

        for(int i = 1; i < l; i++)
            fromBegin[i] = nums[i - 1] * fromBegin[i - 1];

        for(int i = l-2; i >= 0; i--)
            fromEnd[i] = nums[i + 1] * fromEnd[i + 1];

        for(int i = 0; i < l; i++)
            res[i] = fromBegin[i] * fromEnd[i];

        return res;
    }
};

可以化简为

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

        for(int i=0;i<n;i++){
            res[i] *= fromBegin;
            fromBegin *= nums[i];
            res[n-1-i] *= fromLast;
            fromLast *= nums[n-1-i];
        }
        return res;
    }
};