leetcode 238 Product of Array Except Self

这题看似简单，不过两个要求很有意思：

１、不准用除法：最开始我想到的做法是全部乘起来，一项项除，可是中间要是有个０，这做法死得很惨。

２、空间复杂度O(1)：题目说明了返回的那个数组不算进复杂度分析里面

做法：既然不用除法，对于某个数i, result[i] = ０到i - 1的乘积　　X  　 i + 1 到 n - 1的乘积

具体来说，先正向遍历，result[i] 存储的是 0 到i - 1的乘积，再反向遍历，乘上另一半，这就同时满足了时间复杂度和空间复杂度的要求

class Solution {

public:

    vector<int> productExceptSelf(vector<int>& nums) {

        if(nums.empty())

            return vector<int>();

        vector<int> result(nums.size(), 1);

        int accums = 1;

        for(int i = 0; i < nums.size() ; i++){

            result[i] = accums;

            accums *= nums[i];

        }

        accums = 1;

        for(int i = nums.size() - 1; i >= 0; i--){

            result[i] *= accums;

            accums *= nums[i];

        }

        return result;

    }

};