Leetcode 238: 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.)

 题目分析，这个题目要求每个位置除了自己所有其他元素的乘积， 并且要求是contant space complexity, output array不算是extra space， 其实我们就可以利用output array的那个额外的空间来进行求解。 这个题目对于任意位置，是将这个位置之前的所有元素乘积求出来，然后将这个位置之后的所有元素乘积求出来，然后再相乘，这样的算法很容易想到利用两个array， 一个array记录从0-i的乘积， 一个array记录从n-i的乘积，然后任意位置的结果是a1[i] * a2[i-1]， 注意第一个位置和最后一个位置的值，这样是肯定能得出结果的，但是能不能将两个array的空间缩减到一个array的空间呢， 其实是可以的，因为任意一个位置的结果只依赖到这个位置的multiple result 和array1在这个位置之前的值，所以我们可以只利用一个array就可以得到解。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> rst;
        //sanity check
        if (nums.size() <= 1) return rst;
        int mul = 1;
        //initialize
        rst.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            rst.push_back(rst[rst.size()-1]*nums[i]);
        }
        rst[nums.size()-1] = rst[rst.size()-2];
        mul = nums[nums.size()-1];
        for (int i = nums.size()-2; i >= 1; i--) {
            rst[i] = mul * rst[i-1];
            mul = mul*nums[i];
        }
        rst[0] = mul;
        return rst;
    }
};