LintCode - 数组剔除元素后的乘积（容易）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：容易

要求：

给定一个整数数组A。

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。
样例
给出A=[1, 2, 3]，返回 B为[6, 3, 2]

思路：

定义两个数组，一个保存 i 位置左边的乘积，一个保存 i 位置 右边的乘积
比如:
nums: 4 5 2 3 1
left: index: 0 1 2 3 4
value: 1 4 20 60 60
right: index: 0 1 2 3 4
value: 60 15 3 1 1

b[i] = left[i] * right[i]

实现：

public class Solution {
    /*
     * @param nums: Given an integers array A
     * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
  public static List<Long> productExcludeItself(List<Integer> nums) {
        List<Long> ret = new ArrayList();
        if (nums == null) {
            return ret;
        }
        
        //保存左边的乘积
        long[] left = new long[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            if (i == 0) {
                left[i] = 1l;
            } else {
                left[i] = left[i - 1] * nums.get(i - 1);
            }
        }
        
        //保存右边的乘积
        long[] right = new long[nums.size()];
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (i == nums.size() - 1) {
                right[i] = 1l;
            } else {
                right[i] = right[i + 1] * nums.get(i + 1);
            }
        }

        for (int i = 0; i < nums.size(); i++) {
            ret.add(left[i] * right[i]);
        }

        return ret;
    }
}