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.)
这道题不让用乘法，那就只能用把除了自己之外的元素都乘起来的办法。
当然不能每一个元素都完整的算一次，我们需要利用之前的结果。
我们使用两个数组来分别保存每个元素左边数的乘积和右面数的乘积，最后再把两个数组乘起来。
var productExceptSelf = function(nums) {
var left = [];
left[0] = 1;
for(var i=1; i < nums.length; i++)
left[i] = left[i-1] * nums[i-1];
var right = [];
right[nums.length-1]=1;
for(i=nums.length-2; i>=0; i--)
right[i] = right[i+1] * nums[i+1];
for(i=0;i<nums.length-1;i++)
left[i] *= right[i];
return left;
};
但是这样left和right数组都要维护，题目要求只维护一个结果数组。
我们还是先遍历这个数组，得到一个result数组，现在我们得到了所有元素的左边的元素的乘积，就是上面的left数组。
接下来我们从尾部开始遍历这个数组，注意到result[0]是一个可以很好利用的元素，因为随着下标的递减，我们将让它将正好是下标所处元素的右边的数的乘积，我们把这个值乘上result里原有的值就是我们想要的值了。
var productExceptSelf = function(nums) {
var res = [];
res[0] = 1;
for(var i=1; i < nums.length; i++) {
res[i] = res[i-1] * nums[i-1];
}
for(var j = nums.length - 1; j > 0; j--) {
res[j] *= res[0];
res[0] *= nums[j];
}
return res;
};
