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 ofnums 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.)
中心思想：
Dynamic programming
建立两个数组left和right，left用来存在i位上的数左边所有数的乘积left[i]=left[i-1]*nums[i-1]，right用来存在i位上的数右边所有数的乘积。
最后要返还的结果数组result[i] = left[i] * right[i]
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); int left[n]; int right[n]; left[0]=1; right[n-1]=1; for (int i = 1; i < n; i++){ left[i] =left[i-1] * nums[i-1]; } for (int i = n-2; i >=0; i--){ right[i] =right[i+1] * nums[i+1]; } vector<int> result; for (int j = 0; j < n; j++){ result.push_back(left[j]*right[j]); } return result; } };
