题目描述

给定一个数组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(2n)$

公式：Bi = A0A1…Ai-1 * Ai+1…* An-1
要求：常数空间（只能开一个数组），不能用除法
曲线救国：先从左边乘到Ai-1, 再从右边乘到Ai+1

C++ 代码

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        if(A.empty()) return {};

        int n = A.size();
        vector<int> B(n);

        //p代表前i个A[i]的乘积
        for (int i = 0, p=1; i < n; i ++ ){
            B[i] = p;  //B左边赋值 用 = 
            p *= A[i];
        }

        //p代表后i个A[i]的乘积 (技巧: ~i来表示 i>0)
        for(int i=n-1, p=1; ~i; i--){
            B[i] *= p; //B右边赋值要用 *=
            p *= A[i];
        }
        return B;
    }
};