题目描述：
     
    给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 
    
    即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
 

//方法1：暴力遍历求解 

vector<int> multiply(const vector<int>& A) 
{
	vector<int>B;
	int len=A.size();
	for(int i=0;i<len;i++)
	{
		int temp=1;
		for(int j=0;j<len;j++)
		{
			if(i!=j)
				temp*=A[j];	
		}
		B.emplace_back(temp);	
	} 
	return B;
    
}

方法2：矩阵三角区计算

B[i]的值可以看做上图的矩阵中每行的乘积。

下三角用连乘可以很容易求得，先算下三角中的连乘，即先计算出B[i]中的一部分，然后将上三角中的数也乘进去。这样一来就只需要两个循环就可以解决这个问题。时间复杂度是O(n);

其实你只需要知道这个是形成一个矩阵，然后每一行是用来计算B[i],每一行的内容则是A[0]到A[n-1]。利用上三角和下三角进行计算。
 

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int>B(A.size(),1);//声明一个 
        int len=A.size();
        int temp=1;
        for(int i=1;i<len;i++)
        {
            B[i]=B[i-1]*A[i-1];//先计算i之前的乘积，乘积=B[i-1]*A[i-1] ，左下三角 
        } 
        for(int i=len-2;i>=0;i--)
        {
            temp=temp*A[i+1];
            B[i]=B[i]*temp;//先计算i之后的乘积，乘积=B[i]*(temp*A[i+1]) ，右上三角 
        } 
        return B;
    }
};