剑指offer 51-55

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;
    }
}