leetcode-128. 最长连续序列

128. 最长连续序列

• 首先去重，直接把数组装入set集合即可

• 然后，设集合中的某个数为a。遍历集合set

  • 假如这个集合中，存在a-1，说明a不是一个序列的起始值，跳过

  • 如果不存在a-1，说明a是一个连续序列的起始值，再从a开始顺着往下找连续序列，也就是寻找set有无a++，如果有a++就说明连续，temp长度+1

• 不要忘记res最终取最大值

    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();//新建hashset，去重
        int res = 0;//最终连续序列的长度
        for(int num : nums){//把所有数都添加进set
            set.add(num);
        }
        for(int a : set){
            if(set.contains(a - 1)){//如果有a-1就说明 a不是某个连续序列的开头，由于本判断，所有数字在本次循环里只遍历了一遍，时间复杂度O(N)
                continue;
            }
            int temp = 0; //用来记录遍历到a时连续序列的长度
            while(set.contains(a++)){//如果set中没有a-1，说明a是某个连续序列的开头，在set中寻找有无a++，如果有就说明有连续序列
                temp++;
            }
            res = Math.max(temp, res);//维护整体最大值和本次序列最大值
        }
        return res;
    }