给定一个数组 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]。
不能使用除法!
示例:
- 输入: [1,2,3,4,5]
- 输出: [120,60,40,30,24]
提示：
- 所有元素乘积之和不会溢出 32 位整数
- a.length <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
由于不能使用除法，只能在计算B[i]前，分别得到A[0] * A[1] * ... * A[i-1]和A[i+1] * A[i+2] * ... * A[n-1]的值
使用一个dp数组，可以很容易的一趟遍历得到leftSum[i]的值，其中leftSum[i] = a[0] * a[1] * a[2] * ... * a[i-1]
然后进行第二趟逆序遍历，这次遍历可以使用一个临时变量temp存储A[i+1] * A[i+2] * ... * A[n-1]的值，然后将temp * leftSum[i]即可得到B[i]的值
代码：
class Solution {
private:
// leftSum[i] 存储了a[0]*a[1]*...*a[i-1]的积
vector<int> ans;
public:
vector<int> constructArr(vector<int>& a) {
ans.resize(a.size());
if (a.size() == 0) {
return vector<int>();
}
// ans[i]一开始存放leftSum[i]的结果 leftSum[i] = a[0]*a[1]*a[2]*...*a[i-1]
ans[0] = 1;
for (int k = 1; k < a.size(); ++k) {
ans[k] = a[k-1]*ans[k-1];
}
// 计算rightSum[i]
int tmp = 1;
for (int k = (int)a.size()-2; k >= 0; --k) {
tmp *= a[k+1];
ans[k] *= tmp;
}
return ans;
}
};