剑指OfferJZ51：构建乘积数组-java版

JZ51：给定一个数组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] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在

题意为 B[i]=除去A数组的第i个位置的元素A[i],其他位置的数字相乘即可 即为：B[i]=A[0]A[1]…A[i-1]*A[i+1]…A[n-1] 不能使用除法即为：不能使用 (A[0]*A[1]…*A[n-1]) / A[i] 算出B[i]

那么我们把 A[0]A[1]…A[i-1]*A[i+1]…A[n-1] 分成两段来算 分别是 A[0]A[1]…A[i-1] 和A[i+1]…A[n-1] 这两段数都是连续的，我们就可以采用前缀和 和 后缀和求出前段数字乘积和后段数字乘积的乘积

前缀：假设我们有一个字符串ABCD，A、AB、ABC、ABCD 都是这个单词的前缀 后缀：D、DC、DCB、DCBA 都是这个单词的后缀

 public class jz51{
    public int[] multiply(int[] A) {
        int[] f1=new int[A.length];//0到i-1的乘积
        int[] f2=new int[A.length];//i+1到n-1的乘积

        int ans1=1;//0到i-1的乘积
        int ans2=1;//i+1到n-1的乘积
        for(int i=0,j=A.length-1;i