238. Product of Array Except Sel

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，不过写法不够优雅，比较慢，后来改进了性能提升很多，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;
    }
};

不知道为什么反而慢了

或者更简单的写法，只用一个循环

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.