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

知识点：哈希表

题目要求时间复杂度为O(n)，就确定了我们无法使用排序来解决，要想找到最长的连续序列，就需要找到每段序列中最小的元素，我们可以使用Set集合来存储所有的元素，对于一个元素num来说，当集合中不存在num - 1时，说明该元素为序列中最小的元素，我们就可以以此为起点，逐渐增大元素，并且判断是否集合中包含，来确定这段序列的最大长度。看似是使用了两层循环，但第二层循环的进入条件是起始元素为序列最小值，故我们只是将集合遍历了一遍，并没有重复的遍历元素。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tag int整型一维数组 
     * @return int整型
     */
    public int longestConsecutive (int[] tag) {
        // write code here
        int n = tag.length;
        Set<Integer> set = new HashSet<>();
        for(int i: tag) {
            set.add(i);
        }
        int max = 1;
        for(int i: tag) {
            if(!set.contains(i - 1)) {
                int cur = 1;
                while(set.contains(i + cur)) {
                    cur++;
                }
                max = Math.max(max, cur);
            }
        }
        return max;
    }
}