leetCode : Product of Array Except Self

leetCode の「Product of Array Except Self」を解いてみた。
https://leetcode.com/problems/product-of-array-except-self/

この問題は、例えば以下のように、Inputの配列に対して、i 番目の数を除いたすべての積を Output の配列にする、というもの。

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

何も考えずにストレートに実装すると以下のようになるが、これだとAcceptedにはなるもののかなり遅い。。

    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            int tmp = 1;
            for (int j = 0; j < nums.length; j++) {
                if (j == i) {
                    continue;
                }
                tmp *= nums[j];
            }
            output[i] = tmp;
        }
        return output;
    }

結果は以下。

Runtime: 1909 ms
Memory Usage: 47.8 MB

そこで、i 番目を除いた前後の積を事前に計算するようにしてみた。具体的には以下。

    public int[] productExceptSelf(int[] nums) {
        int[] before = new int[nums.length];
        int[] after = new int[nums.length];

        before[0] = 1;
        after[nums.length - 1] = 1;
        for (int i = 1; i < nums.length; i++) {
            int j = nums.length - i - 1;
            before[i] = before[i - 1] * nums[i - 1];
            after[j] = after[j + 1] * nums[j + 1];
        }

        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = before[i] * after[i];
        }

        return result;
    }

これだと、以下のように格段に速くなった。

Runtime: 2 ms
Memory Usage: 47.6 MB

この、事前に計算しておいて、後の計算量を減らす考え方は「累積和」に近いかな。