版权声明：本文为博主原创文章，未经博主允许不得转载。
难度：容易
要求：
给定一个整数数组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;
}
}
