Problem:
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.)
Subscribe to see which companies asked this question
1 class Solution { 2 public: 3 vector<int> productExceptSelf(vector<int>& nums) { 4 5 /* 6 思路:left[i]表示i之前的数的乘积 7 right[i]表示i之后的数的乘积 8 那么total[i] = left[i]*right[i] 9 扫面两遍数组出结果 10 */ 11 12 vector<int> left(nums.size(),1); 13 14 for(int i=1;i<nums.size();i++) 15 { 16 left[i]=left[i-1]*nums[i-1]; 17 } 18 19 int right=1; 20 21 for(int i=nums.size()-2;i>=0;i--) 22 { 23 right=nums[i+1]*right; 24 left[i]*=right; 25 } 26 27 return left; 28 29 30 } 31 };
LeetCode:Product of Array Except Self
原文：http://www.cnblogs.com/xiaoying1245970347/p/5132651.html