51.构建乘积数组
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。
不能使用除法。（注意：规定B[0]和B[n-1] = 1）
通过B[i]的构成不难发现它总由左右两个部分组成，所以我们可以用两个辅助数组，一个数组left用来存从0到i-1的所有乘积，一个数组right用来存length-1到i+1的所有乘积，然后B[i]=left[i-1]*right[i+1]即可。
代码如下
public class Solution {
public int[] multiply(int[] A) {
int length = A.length;
int[] left = new int[length];
int[] right = new int[length];
int[] res = new int[length];
left[0] = A[0];
right[length-1] = A[length-1];
for(int i = 1;i<length-1;i++){
left[i] = A[i]*left[i-1];
}
for(int j = length-2;j>0;j--){
right[j] = A[j]*right[j+1];
}
res[0] = right[1];
res[length-1] = left[length-2];
for(int k=1;k<length-1;k++){
res[k] = left[k-1]*right[k+1];
}
return res;
}
}
