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;
    }

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

分治法的思路，由于不能用除法，所以先算出數(shù)組所有元素的乘積再除以對應(yīng)位置的數(shù)字的方法行不通。規(guī)定了時間復(fù)雜度不超過O(n)，所以遍歷兩次（外循環(huán)是位置，內(nèi)循環(huán)是除該位置的元素乘積）也不行。所以有些天才就想出了分治法的思路。

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

上面的對角線就是該位置的元素值，除去它自己意味著該元素可以當(dāng)作1來看待。第一步，先完成1左邊位置的元素的乘積，記錄在數(shù)組中。第二步，再完成1右邊位置元素的乘積，記錄在數(shù)組中。第三步，左右乘積數(shù)組相乘合并，即為結(jié)果數(shù)組。

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];

進一步要求常量級空間復(fù)雜度，可以使用結(jié)果數(shù)組來存儲左邊位置元素的乘積，使用right變量來累計右邊位置的乘積。第一次遍歷，res存儲了左邊位置乘積的值，第二次遍歷，每次right要累計右邊位置的乘積，這樣就確保了空間復(fù)雜度為O(1)。