剑指offer 74- 构建乘积数组

给定一个数组，请构建一个数组，其中中的元素。

不能使用除法。

样例

输入：[1, 2, 3, 4, 5]

输出：[120, 60, 40, 30, 24]

思考题：
能不能只使用常数空间？（除了输出的数组之外）

分析：
可以分两部分来算

时间复杂度：

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        if(A.empty()) return {};
        int n = A.size();
        vector<int> B(n);
        for(int i=0, p = 1; i<n; i++) B[i] = p, p*=A[i];
        for(int i=n-1, p = 1; i>=0; i--) B[i] *= p, p *= A[i];
        return B;
    }
};