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].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
题目含义：给一个数组nums[n],返回一个数组output[n] output[i]等于全部数的乘积nums[0...n]除开nums[i]
不能用除法 时间复杂度为o(n)
思想：
定义两个数组left[n] right[n] 分别表示i的左边值得乘积和右边值得乘积
c++ AC代码：
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> right(len);
vector<int> left(len);
right[0]=left[len-1]=1;
for(int i =1;i<len;i++){
right[i] = right[i-1]*nums[i-1];
left[len-i-1] = left[len-i]*nums[len-i];
}
for(int i=0;i<len;i++){
nums[i]=right[i]*left[i];
}
return nums;
}
};
