LeetCode OJ 之 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].

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

1、先求出总的乘积，再除以当前数（注意当前数为0的情况）（效率不高）

2、第一次遍历保存前i个数字的乘积，第二次从后遍历保存一个数表示后j个乘积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        vector<int> result;
        long long pro = 1;
        int len = nums.size();
        for(int i = 0 ; i < len ; i++)
            pro *= nums[i];
        for(int j = 0 ; j < len ; j++)
        {
            if(nums[j] != 0)
                result.push_back(pro/nums[j]);
            else
            {
                int tmpPro = 1;
                for(int k = 0 ; k < len ; k++)
                {
                    if(k != j)
                        tmpPro *= nums[k];
                }
                result.push_back(tmpPro);
            }
        }
        return result;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int len = nums.size();
        vector<int> result(len , 0);
        result[0] = 1;
        for(int i = 1 ; i < len ; i++)
        {
            result[i] = result[i-1] * nums[i-1];    //result存储的是0~i-1总共i个数字的乘积
        }
        int postPro = 1;
        for(int j = len-1 ; j >= 0 ; j--)
        {
            result[j] *= postPro;
            postPro *= nums[j]; //postPro表示从j到len-1个数字的乘积
        }
        return result;
    }
};