剑指Offer 66.构建乘积数组

给定一个数组 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;
    }
                    
    
};