剑指 Offer 66. 构建乘积数组

思路

方法：对称遍历

 

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        if(a.empty())
            return vector<int>();
            
        vector<int> b(a.size());
        b[0] = 1;

        for(int i = 1; i < b.size(); ++i) {
            b[i] = b[i-1] * a[i-1];
        } 

        int tmp = 1;
        for(int i = b.size()-2; i >= 0; --i) {
            tmp *= a[i+1];
            b[i] *= tmp;
        }

        return b;
    }
};

参考

面试题66. 构建乘积数组（表格分区，清晰图解）