Leetcode题解 剑指 Offer 66. 构建乘积数组

PROBLEM

剑指 Offer 66. 构建乘积数组

难度 中等

MY ANSWER

双循环计算时间复杂度为O(n^2)，TLE。

BETTER SOLUTION

思路如图，时间复杂度为O(n)，下三角乘积使用res数组来储存，上三角乘积使用一个变量存储，空间复杂度降低到常数。

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        if(a.empty()) {
            return {};
        }
        vector<int> res(a.size(), 1);
        int tmp = 1;
        for(int i = 1; i < res.size(); i++) {
            res[i] = res[i-1] * a[i-1];
        }
        for(int i = res.size() - 2; i >= 0; i--) {
            tmp *= a[i+1];
            res[i] *= tmp;
        }
        return res;
    }
};

SUMMARY

使用上一步计算结果来减少重复计算，使用结果数组和变量存储中间变量减少空间复杂度。