238. Product of Array Except Self

Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].

Solve itwithout divisionand 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 arraydoes notcount as extra space for the purpose of space complexity analysis.)

解题方法

透過從左到右 和從右到左

    /*Using product from left to right and using product from right to left
    Function: num[i] = left[i - 1] * right[i + 1] 

    O(n + n + n) = O(n)
    */
    public int[] productExceptSelf(int[] nums) {
        if(nums == null || nums.length == 0){ return new int[]{};}
        if(nums.length == 1){ return nums;}

        int n = nums.length;  
        int[] ans = new int[n];
        ans[0] = 1;
        for(int i = 1; i < n; i++){
            ans[i] = ans[i - 1] * nums[i - 1];
        }
        int right = 1;
        for(int i = n - 1; i >= 0; i--){ //*********************
            ans[i] *= right;
            right *= nums[i];
        }
        return ans;
    }