238. Product of Array Except Self

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

思考：不用除法,怎么實現(xiàn) ? time O(n) space O(1)

    /*
    Wrong 我的方法1: 全部相乘，再除以當(dāng)前元素。這樣有個問題，如果當(dāng)前為0，結(jié)果不對
    */
    public int[] productExceptSelf_my(int[] nums) {
        int[] res = new int[nums.length];
        int sum = 1;
        for(int item:nums){
            if(item != 0){
                sum *= item;
            }            
        }
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 0){
                res[i] = sum;
            }else{
                res[i] = sum/nums[i];
            }
        }
        return res;
    }

/*
        
        Right 答案方法: 先計算左側(cè) 乘積left,再計算右側(cè)乘積right; 結(jié)果 = left * right
        o[i] = a[0]a[1]...a[i-1]  * a[i+1]...a[n-1]
    */
    public int[] productExceptSelf_solution(int[] nums) {
        int[] res = new int[nums.length];
        //初始化為1
        for(int i = 0; i < nums.length; i++){
            res[i] = 1;
        }
        
        //計算left數(shù)組
        int left = 1;
        for(int i = 1; i < nums.length;i++){
            left = left * nums[i - 1];
            res[i] = res[i] * left;
        }
        //計算right
        int right = 1;
        for(int i = nums.length - 2; i >= 0;i--){
            right = right * nums[i+1];
            res[i] = res[i] * right;
        }
        return res;
    }