题解 | #构建乘积数组#

先写一种暴力解法。使用二重循环遍历数组，将对应结果插入结果集。
这种做法时间复杂度为O(n^2)，空间复杂度O(1)，显然还有改进空间。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> result;
        for(int i = 0;i < A.size();i++){
            int temp = 1;
            for(int j = 0;j < A.size();j++){
                if(j != i){
                    temp *= A.at(j);
                }
            }
            result.push_back(temp);
        }
        return result;
    }
};

解析来考虑更好的解法。
观察结果的生成方式，发现结果的算式可以构成一个矩阵，且其对角线为全1，并且每一列在对角线之外的地方都相等。
发现其递推规律。从而得到以下解法。
先循环一次算出结果项在对角线左侧的值，在循环一次乘上右侧的值，即得结果。
其时间复杂度为O(n)，空间复杂度为O(1)。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> result(A.size(),1);
        for(int i = 1;i < A.size();i++){
            result.at(i) = result.at(i - 1) * A.at(i - 1);
        }
        int temp = 1;
        for(int i = A.size() - 2;i > -1;i--){
            temp *= A.at(i + 1);
            result.at(i) *= temp;
        }
        return result;
    }
};