题目
给定一个数组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]
思考题：
能不能只使用常数空间？（除了输出的数组之外）

解法：前后缀分解

分成左右两部分分开乘
时间复杂度O(n)，空间复杂度O(1)

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