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

解题方法

使用從右到左的乘積紀錄 與 從左到右的遍歷紀錄去計算得到自己以外的乘積．

    public int[] productExceptSelf(int[] nums) {
        //corner case
        if(nums == null || nums.length == 0){
            return new int[]{};
        }

        int n = nums.length;
        int[] product = new int[n];
        product[n - 1] = nums[n - 1];
        for(int i = n - 2; i >= 0; i--){
            product[i] = nums[i];
            product[i] = product[i + 1] * product[i];
        }

        int cur = 1;
        int[] ans = new int[n];
        for(int i = 0; i < n - 1; i++){
            ans[i] = cur * product[i + 1];
            cur = cur * nums[i];
        }
        ans[n - 1] = cur;
        return ans;
    }