Product of Array Except Self 题解

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;    }};