题解 | #牛牛的和平年代#

思路：

题目的主要信息（直接看题意，背景不重要）：

对于数组mSet，每次以前 $i$ 个元素为一个集合，如果集合中出现了最小数到最大数中的所有元素，则返回true，否则返回false
需要判断每一个前缀是否为true，第一个元素一定是true

方法一：排序+暴力解法
具体做法：
遍历数组mSet，每次将新元素加入辅助数组，然后对辅助数组进行排序，排成递增序。然后遍历辅助数组，如果出现前后两个数相差大于1，则一定为false，遇到相差为1的元素，计数器加一，最后如果计数器等于尾元素减首元素说明填满了这其中所有的元素，是返回true。

class Solution {
public:
    vector<bool> continuousSet(vector<int>& mSet) {
        vector<bool> res;
        vector<int> temp; //临时数组，每次记录到i的长度的mSet数组
        if(mSet.size() == 0)
            return res;
        res.push_back(true); //第一个一定为true
        temp.push_back(mSet[0]);
        for(int i = 1; i < mSet.size(); i++){
            temp.push_back(mSet[i]); //加入当前元素后排序
            sort(temp.begin(), temp.end());
            int gap = 0;
            for(int j = 1; j < temp.size(); j++){
                if(temp[j] - temp[j - 1] > 1){ //差距大于1，说明有间隔元素
                    res.push_back(false);
                    break;
                }
                if(temp[j] != temp[j - 1]) //这里是相差为1
                    gap++;
            }
            if(gap == temp[temp.size() - 1] - temp[0]) //相差刚好是尾减去首，说明填满
                res.push_back(true);
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^2log_2n)$ ，完整的复杂度应该是 $O(n(nlog_2n+n))$ ，省略了低次幂
空间复杂度： $O(n)$ ，辅助数组temp，res是必要空间，不属于额外空间

方法二：哈希表
具体做法：
我们想要知道的是每次前缀的最大元素 $max$ 和最小元素 $min$ 之间是否被填满了，如果前缀中不同的元素一共有 $(max-min+1)$ 个，那么就一定填满，否则不行。因此我们可以想到用哈希表统计每个元素出现的次数，哈希表的大小就是不同元素的个数。
图片说明

class Solution {
public:
    vector<bool> continuousSet(vector<int>& mSet) {
        vector<bool> res;
        unordered_map<int, int> mp; //哈希表记录重复数组，即出现了多少不同的数字
        int maxnum = mSet[0];
        int minnum = mSet[0];
        for(int i = 0; i < mSet.size(); i++){
            maxnum = max(maxnum, mSet[i]); //更新最大值最小值
            minnum = min(minnum, mSet[i]);
            mp[mSet[i]]++;
            if(maxnum - minnum + 1 == mp.size()) //哈希表中的元素刚好填满最大值到最小值
                res.push_back(true);
            else
                res.push_back(false);
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历一次数组， $n$ 为数组长度
空间复杂度： $O(n)$ ，最坏情况下所有元素都不同，哈希表大小为 $O(n)$