LeetCode Note Java 00238：Product of Array Except Self

回傳一個 Array，其每一項等於輸入 Array 的每一項排除自己後的乘積。須滿足 O(n) 時間複雜度，且不得使用除法。

題目

Product of Array Except Self Medium

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

解法

• 限制 O(n) 意味著不準暴力法，並且在常數次的 for loop 下要完成計算。
• 禁止除法意味著每次 for loop 不能乘到每個數字。

這樣限制後逼得我們想出 Array 的每一格都是左邊所有數字的乘積乘上右邊所有乘積的方式。
要做到這種事最簡單的方法是從左到右乘一次，再從右到左乘一次，我是覺得不好想，但用代入法來看確實就是答案。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        int left = 1, right = 1; // 從左到右跟從右到左要乘的數字
        for (int i = 0; i < nums.length; i++) { // 從左到右
            output[i] = left; // 第一圈時 left 是 1
            left *= nums[i]; // left 每走一格就乘上那格的值
        }
        for (int i = nums.length - 1; i > -1; i--) { // 從右到左
            output[i] *= right; // 第一圈時 right 是 1
            right *= nums[i]; // right 每走一格就乘上那格的值
        }
        return output;
    }
}

參考資料

leetcode/java/0238-product-of-array-except-self.java