构建乘积数组

给定一个数组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中的每个元素要乘的元素写成矩阵，其中A[i]置1，那么就是一个上三角和一个下三角，类似于下图：

那么B[i]就可以表示成C[i]*D[i]，就可以解决了。

代码：

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B,C,D;
        int len = A.size();
        int t1=1,t2=1;
        if(len==0)
            return B;
        C.push_back(t1);
        D.push_back(t2);
        for(int i=0;i<len-1;i++){
            t1*=A[i];
            t2*=A[len-1-i];
            C.push_back(t1);
            D.push_back(t2);
        }
        for(int j=0;j<len;j++)
            B.push_back(C[j]*D[len-1-j]);
        return B;
    }
};

进行代码优化：//不用再分配C,D的空间，节省了空间

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B;
        int len = A.size();
        int tem=1;
        if(len==0)
            return B;
        B.push_back(tem);
        for(int i=0;i<len-1;i++){
            tem*=A[i];
            B.push_back(tem);
        }
        tem=1;
        for(int j=len-2;j>=0;j--){
            tem*=A[j+1];
            B[j]*=tem;
        }
        return B;
    }
};