题目描述
给定一个数组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];）
背景：B数组有n个值，每个值要进行一次连乘，因此正常连乘的话时间复杂度为O(n^2)，效率非常低。考虑到计算每个B[i]时都会有重复，思考B[i]之间的联系，找出规律，提高效率。 PS:盗张图
图片说明
思路：B[i]的左边和B[i-1]有关，右边和B[i+1]有关。
B[i]=A[0] * A[1]... * A[i-1]乘上A[i+1]...A[n-1] 以A[i]为分界线，将B分为左右两个部分相乘。
B[i]=左 * 右 利用一轮循环计算所有的左下三角，一轮循环计算所有的右上三角
当把A[0]...A[n-2]利用一轮for循环算出来时，左下角的所有乘积都知道了（得到了n-1个值），同理一轮for循环，右上角的A[1]...A[n-1]所有乘积都知道了（也得到了n-1个值），因此在第两轮for循环之时，进行对应的“组装”就可以得到对应的B[i]的值，相当于两轮循环下来，就可以完成所有计算。可以看到由于循环时分别得到n-1个值，因此n>1。因此需要加上判断条件

public class Solution {
    public int[] multiply(int[] A) {
        if(A==null || A.length<2)
            return null;
        int[] B=new int[A.length];
        B[0]=1;
  //这一轮循环下来，B数组中暂时存放了自己对应左下三角的乘积
  //即自己分成了左右两部分相乘后，左边部分的值此时拿到了
        for(int i=1;i<A.length;i++)
            B[i]=B[i-1]*A[i-1];
        int temp=1;
        for(int i=A.length-2;i>=0;i--){
            temp*=A[i+1];
          //temp =temp*A[i+1]; temp就是i位置对应的右边部分的值 从A[n-1]一直乘到A[1]
            B[i]*=temp;
          //B[i] =B[i]*temp; 左边部分乘上右边部分
        }
        return B;
    }
}