题目

题目链接

https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked

解题思路

把数组中所有的数字存放到哈希表中。不断地遍历哈希表。当遍历到的点是子序列起点，则不断地+1，判断元素是否在序列中。
$$时间复杂度：O(n)$$
时间复杂度看似好像是N^2,但是实际上那些不是起点的节点跳过了。

相关代码

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0) return 0;
        //创建一个哈希表
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++) set.add(nums[i]);

        int res=0;
        int length=1;
        for(int num:set){
            if(set.contains(num-1)==true) continue;
            int temp = num;

            while(set.contains(temp+1)==true){
                temp=temp+1;
                length++;
            }        
            if(set.contains(temp+1)==false){
                res=Math.max(res,length);
                length=1;
            }
        }
        res = Math.max(res,length);
        return res;
    }
}