题解 | #连续的牛群标签序列# 哈希表

知识点

哈希表

思路

原数组中存在的数放到数轴上的话，其实是一段一段的。我们要求的是最长段的长度。

我们可以把原数组放到哈希表中，逐个枚举每一段的开头元素，然后向后延伸，找到每一段的长度后更新答案。

由于原数组是一段一段的，所以我们最后的遍历次数其实是的，整体时间复杂度为

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tag int整型vector 
     * @return int整型
     */
    int longestConsecutive(vector<int>& tag) {
        unordered_set<int> S(tag.begin(), tag.end());
        int res = 0;
        for (auto x : tag) {
            if (!S.count(x - 1)) {
                int cur = x;
                int len = 1;
                while (S.count(cur + 1)) {
                    cur += 1;
                    len += 1;
                }
                res = max(res, len);
            }
        }
        return res;
    }
};