构建乘积数组
给定一个数组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]。不能使用除法。（点我直接练习）
分析
思路一开始局限在了暴力法，即每个输出的数值都做一遍乘法，一个循环可以搞定，总乘法次数是n x n x n 。在参考了别人的思路以后，才豁然开朗本题的正确姿势——构建累成数组。即新构建两个数组B0，B1。使得B[i] = B0[i] x B1[i]。 这样构建后，总的乘法次数是3n,这样就少很多了。要搞清楚两个新数组如何建立也不难。依旧使用递推思路，借一张图来表示：
对角线的位置及A[i]的位置，所以B0构建对角线左侧的乘积，B1则构建对角线右侧的乘积即可。构建对角线左侧即正向累成，使用正向循环；构建对角线右侧即反向累成，那么相应的，反向循环即可。
使用到的知识点
C++
数组（向量）构建
Python
暴力法，没什么知识点
题解
C++(Clang++ 3.9) : 运行时间：5ms 占用内存：508k
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int n = A.size();
vector<int> B0(n,1);
vector<int> B1(n,1);
vector<int> B(n,1);
for(int i = 1;i<n;++i)
B0[i] = B0[i-1] * A[i-1];
for(int i = n-2;i>=0;--i)
B1[i] = B1[i+1] * A[i+1];
for(int i = 0;i<n;++i)
B[i] = B0[i]*B1[i];
return B;
}
};
Python 2.7-运行时间：36ms ,占用内存：6214k
class Solution:
def multiply(self, A):
B = A[:]
for m in range(len(A)):
sum = 1
for i in range(len(A)):
if i != m:
sum = sum*A[i]
B[m] = sum
return B
