剑指offer51：构建乘积数组 (Leetcode66)
解法一：基于两层for循环的暴力法(超出时间限制)
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int Size = A.size();
vector<int> B(Size, 1);
for (int i = 0; i<Size; i++)
{
for (int j = 0; j<Size; j++)
{
if (j != i)
B[i] *= A[j];
}
}
return B;

}
};

解法二：基于对称遍历 (执行用时48ms,内存消耗24.6MB)
class Solution2 {
public:
vector<int> constructArr(vector<int>& a) {
int n = a.size();
vector<int> ret(n, 1);
int left = 1;
for (int i = 0; i < n; i++) {
ret[i] = left;
left = left * a[i];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
ret[i] *= right;
right *= a[i];
}
return ret;
}
};