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.)

思路分析：基本思路是用两个数组left和right，left保存从最左側到当前数之前的全部数字的乘积。right保存从最右側到当前之后的全部数字的乘积。然后，结果数组就是把这两个数组相应位置相乘就可以。假设想仅仅是用O（1）的space。就须要复用输入和输出数组的空间。基本思路是。先计算right数组，利用result数组的空间保存，然后计算left数组。仅仅须要一个变量left保存当前从最左側到当前数字之前的全部数字之和。

总之，使用好输入输出数组的空间，避免使用很多其它space。下面凝视部分code给出了O（n） 空间复杂度的解法，非凝视部分给出了O（1）空间复杂度的解法。

时间复杂度就是O（n）。

AC Code：

public class Solution {    public int[] productExceptSelf(int[] nums) {        /*int len = nums.length;        int [] res = new int[len];                if(len < 2) return res;                int [] left = new int[len];        int [] right = new int[len];                left[0] = 1;        right[len - 1] = 1;        for(int i = len - 1; i > 0; i--){            right[i - 1] = right[i] * nums[i];        }                for(int i = 0; i < len - 1; i++){            left[i + 1] = left[i] * nums[i];        }                for(int i = 0; i < len; i++){            res[i] = left[i] * right[i];        }        return res;*/                int len = nums.length;        int [] res = new int[len];                if(len < 2) return res;        res[len - 1] = 1;        for(int i = len - 1; i > 0; i--){            res[i - 1] = res[i] * nums[i];        }                int left = 1;        for(int i = 0; i < len; i++){            res[i] *= left;            left = left * nums[i];                    }                return res;    }}