238. Product of Array Except Self

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret(nums.size());
        ret.front() = 1;
        for(int i = 1; i < nums.size(); ++i)
            ret[i] = ret[i - 1] * nums[i - 1];
        int right = 1;
        for(int i = nums.size() - 2; i >= 0; --i)
        {
            ret[i] *= right * nums[i + 1];
            right *= nums[i + 1];
        }
        return ret;
    }
};

对于数

1
2
3

Numbers:     2    3    4     5
Lefts:            2  2*3 2*3*4
Rights:  3*4*5  4*5    5

由此可见对于一个数的乘积，只需要计算他左边所有数的乘积和右边所有数的乘积，两者相乘就可以获得除了这个数外的乘积，而对于每一位来说，左右乘积都可以通过O(n)的两次遍历来达到，O(n)space的算法就是把左右的乘积放到left和right两个数组中

如果要将O(n)space降低到O(1)space，就需要把左乘积先存放在返回的数组中，然后从右往前遍历，对于每一个位置都在每次遍历时计算出一个右乘积，这个乘积ret中保存的左乘积，就可以直接得到答案