238. Product of Array Except Self

problem description

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]
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.)

algorithm thought

本来这题最简单的解决办法就是将所有的乘起来，然后每次除一个数，就能得到结果。但是follow up明确静止这么做。为了在O(n)时间做完，还是得先保存一些结果。

定义一个left和一个right数组。保存从最左边和最右边开始，连续数的乘积。将所有的乘积都保存之后，再次遍历数组，就能在O(1)时间算出每个位置应该填的值了。

code

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

algorithm analysis

时间复杂度O(n)，只需要3次遍历数组。空间复杂度O(n)，用了两个vector来保存数据。