238. PRoduct of Array Except Self

題目描述：

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

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

題目鏈接：238. Product of Array Except Self

算法描述：

    根據題意，給出一個數組，我們將返回一個結果數組，該結果數組中第 i 個元素的值為除去第 i 個元素的所有其它元素之積。題目要求復雜度控制在 O（n），并且不能用除法。

代碼：

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