Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

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

这个题,刚一开始只能想到暴力方法,即对每个位置之外的元素累乘。后来想想如何保存一些重复乘过的值呢,重复利用的话便可以减少计算的次数,提高速度。于是便使用两个数组来保存左右两个方向上的累积,每个位置的结果便是这两个数组对应位置的乘积。

另外,如果还可以将一个方向上的累积直接乘在另一个方向的结果上,在这两次循环后,得到的数组即是最终结果,这样便可以省去额外的空间。

/*
 * 238. Product of Array Except Self
 * https://leetcode.com/problems/product-of-array-except-self/
 * https://realneo.me/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;
    }
}