给定一个含有 n 个整数的数组 nums，n > 1，返回一个数组 output，其中 output[i] 等于 nums 数组中除去 nums[i] 之外所有数字的乘积。

举例：
输入： [1,2,3,4]
输出： [24,12,8,6]

这个题，刚一开始只能想到暴力方法，即对每个位置之外的元素累乘。后来想想如何保存一些重复乘过的值呢，重复利用的话便可以减少计算的次数，提高速度。于是便使用两个数组来保存左右两个方向上的累积，每个位置的结果便是这两个数组对应位置的乘积。
另外，如果还可以将一个方向上的累积直接乘在另一个方向的结果上，在这两次循环后，得到的数组即是最终结果，这样便可以省去额外的空间。

/*
 * 238. Product of Array Except Self
 * https://leetcode.com/problems/product-of-array-except-self/
 * https://www.whosneo.com/238-product-of-array-except-self/
 */

import java.util.Arrays;

public class ProductExceptSelf {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};

        ProductExceptSelf solution = new ProductExceptSelf();

        int[] result = solution.productExceptSelf(nums);
        System.out.println(Arrays.toString(result));
    }

    private int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] result = new int[length];

        int[] left = new int[length];
        int[] right = new int[length];
        left[0] = 1;
        right[length - 1] = 1;

        for (int i = 1; i < length; i++) {
            left[i] = left[i - 1] * nums[i - 1];
            right[length - 1 - i] = right[length - i] * nums[length - i];
        }

        for (int i = 0; i < length; i++)
            result[i] = left[i] * right[i];

        return result;
    }
}