Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:

• Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Solution: 不能用除法的方法

1. 為什么不能用除法的方法。

   • 比如[0 ,1], 如果先把所有乘起來，再除以本身。那么結(jié)果是[0, 0]。錯(cuò)誤。
   • 如果乘積的時(shí)候排除0，乘積為1，再除以本身。那么結(jié)果是[1, 1]。錯(cuò)誤。
   • 所以這種方法無法滿足所有case

2. 用類似water trapping的方法

   • 對(duì)每個(gè)元素，用2個(gè)數(shù)組，分別存其左邊元素的積 和 其右邊元素的積。
   • 結(jié)果就是，左邊積 * 右邊積。 但是空間復(fù)雜度不合符

3. 優(yōu)化，其實(shí)可以只用一個(gè)array來存結(jié)果，先從左到右，求出每個(gè)元素左邊的積和
   再從右到左，用一個(gè)變量存每個(gè)元素右邊的積，再與當(dāng)前result[i]相乘，來覆蓋 result[i]

1. 未優(yōu)化空間復(fù)雜度

 //  Solution 1: Space O(n)
// 對(duì)每個(gè)元素，用2個(gè)數(shù)組，分別存其左邊元素的積 和 其右邊元素的積。
// 結(jié)果就是，左邊積 * 右邊積。 但是空間復(fù)雜度不合符。
// 優(yōu)化，其實(shí)可以只用一個(gè)array來存結(jié)果，先從左到右，求出每個(gè)元素左邊的積和
// 再從右到左，有一個(gè)變量存每個(gè)元素右邊的積，再與當(dāng)前result[i]相乘，===》 replace result[i]
class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0)
            return nums;
        
       
        int[] productToLeft = new int[nums.length];
        int[] productToRight = new int[nums.length];
        
        //1. construct each num's left nums product
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                productToLeft[i] = 1;
                continue;
            }
               
            productToLeft[i] = productToLeft[i - 1] * nums[i - 1];
        }
        
        //2. construct each num's right nums product
        for (int i = nums.length - 1; i >= 0 ; i--) {
            if (i == nums.length - 1) {
                productToRight[i] = 1;
                continue;
            }
               
            
            productToRight[i] = productToRight[i + 1] * nums[i + 1];
        }
        
        for (int i = 0; i < nums.length; i++) {            
            productToLeft[i] = productToLeft[i] * productToRight[i];
        }
        
        return productToLeft;
    }
}

2. 優(yōu)化空間復(fù)雜度

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0)
            return nums;
        
        int[] result = new int[nums.length];
        result[0] = 1;
        
        //1. left to right: construct toLeftProduct of each num
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        //2. right to left: construct toRightProduct of each num
        int prevProduct = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            prevProduct = prevProduct * nums[i + 1];
            result[i] = result[i] * prevProduct;
        }
        
        return result;
    }
}