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

Example:

Input: [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

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

一開始看到不能用division的時候想到的是必須對某一段的product做提前記錄。想到的辦法比如recursion+hash，比如tree。卡在tree這個思路上一會兒，想的是類似sum tree的product tree。build tree是O(n)，但是最壞的情況，某個元素算左右product需要log(N)。ps，事后想想其實第一個思路更正確。

之后想到左右vector，不過寫法不夠優(yōu)雅，比較慢，后來改進了性能提升很多，10%提升到60%多，看答案也把答案寫簡練了。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        
        vector<int> left_prod(len,1);
        vector<int> right_prod(len,1);
        
        for (int i=1; i<len; ++i) {
            left_prod[i] = left_prod[i-1] * nums[i-1];
            right_prod[len-1-i] = right_prod[len-i] * nums[len-i];
        }
        
        vector<int> ans(len,1);
        for (int i=0; i<len; ++i) {
            ans[i] = left_prod[i] * right_prod[i];
        }
        
        return ans;
    }
};

Runtime: 44 ms, faster than 47.90% of C++ online submissions for Product of Array Except Self.
Memory Usage: 25.4 MB, less than 24.96% of C++ online submissions for Product of Array Except Self.

官方答案里面除了上面這個方法，還有一種思路是不用right_prod這個vector

我的默寫：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        
        vector<int> left_prod(len,1);
        
        for (int i=1; i<len; ++i) {
            left_prod[i] = left_prod[i-1] * nums[i-1];
        }
        
        int right_prod = 1;
        for (int i=1; i<len; ++i) {
            right_prod *= nums[len-i];
            left_prod[len-1-i] *= right_prod;
        }
        
        return left_prod;
    }
};

不知道為什么反而慢了

或者更簡單的寫法，只用一個循環(huán)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        
        int left_prod = 1;
        int right_prod = 1;
        vector<int> ans(len,1);
        
        for (int i=1; i<len; ++i) {
            
            left_prod *= nums[i-1];
            ans[i] *= left_prod;
            
            right_prod *= nums[len-i];
            ans[len-1-i] *= right_prod;
        }
        
        return ans;
    }
};

Runtime: 40 ms, faster than 66.30% of C++ online submissions for Product of Array Except Self.
Memory Usage: 24.2 MB, less than 72.35% of C++ online submissions for Product of Array Except Self.