Description:
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).
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.)
Example:
For example, given [1,2,3,4], return [24,12,8,6].
Link:
https://leetcode.com/problems/product-of-array-except-self/#/description
解题方法：
扫描两次数组：
第一次从左往右扫描，记录从0 ~ i-1的积。
第二次从右往左扫描，记录从n-1 ~ i+1的积。
将两次扫描的结果对应的位置相乘得到所求的数组。
Tips:
如果出了输出数组不能用额外的空间。则可以用输出数组记录两次扫描的结果。并在第二次扫描的时候将结果算出来。
Time Complexity：
时间O(N) 空间O(1)
完整代码：
vector<int> productExceptSelf(vector<int>& nums)
{
int len = nums.size();
vector<int> result;
if(len == 0)
return result;
int sum = 1;
for(int i = 0; i < len; i++)
{
result.push_back(sum);
sum *= nums[i];
}
for(int i = len-1, sum = 1; i >= 0; i--)
{
result[i] *= sum; //直接算出结果
sum *= nums[i];
}
return result;
}
