Amazon-Product of Array Except S

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

Solution:

public int[] productExceptSelf(int[] nums) {
        if(nums==null||nums.length==0) return null;
        
        int n=nums.length;
        int[] res=new int[n];
        res[0]=1;
        for(int i=1;i<n;i++){
            res[i]=res[i-1]*nums[i-1];
        }
        int right=1;
        for(int i=n-1;i>=0;i--){
            res[i]*=right;
            right*=nums[i];
        }
        return res;
    }

时间复杂度：O(n)
空间复杂度：O(1)

分治法的思路，由于不能用除法，所以先算出数组所有元素的乘积再除以对应位置的数字的方法行不通。规定了时间复杂度不超过O(n)，所以遍历两次（外循环是位置，内循环是除该位置的元素乘积）也不行。所以有些天才就想出了分治法的思路。

  1 2 3 4
1 1 
2   1
3     1
4       1

上面的对角线就是该位置的元素值，除去它自己意味着该元素可以当作1来看待。第一步，先完成1左边位置的元素的乘积，记录在数组中。第二步，再完成1右边位置元素的乘积，记录在数组中。第三步，左右乘积数组相乘合并，即为结果数组。

left[i]=left[i-1]*nums[i-1];  0<i<n
right[i]=right[i+1]*nums[i+1];  n-1>i>=0
res[i]=left[i]*right[i];

进一步要求常量级空间复杂度，可以使用结果数组来存储左边位置元素的乘积，使用right变量来累计右边位置的乘积。第一次遍历，res存储了左边位置乘积的值，第二次遍历，每次right要累计右边位置的乘积，这样就确保了空间复杂度为O(1)。