[leetCode 128] 最长连续序列

解题思路

首先，用一个set来存储所有的元素，这样我们可以方便的判断某个数在不在这个数组里面。

然后，从前往后遍历这个set，针对set里面的每个元素x，我们都判断一下x+1，x+2…在不在set里面，找到以x为起点的最长子串。

然后，更新最长距离即可。这个过程的时间复杂度是O(n^2)，因为我们针对每一个数，都有可能要遍历n次。

所以，我们考虑优化：针对数x，如果它是某个连续的子序列的起点，就往后遍历；如果它是某个子序列的中间的数，那么就不需要遍历了。

那么怎么判断一个数是不是某个子序列的中间数呢？只需要判断这个数的前一个数在不在集合里面就可以了，也就是看看x-1在不在，如果在，就直接跳过这个数就可以了。

代码

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (var a : nums)
            set.add(a);
        int max=0;
        for (var i : set){
            if (set.contains(i-1)) continue;
            int t=1;
            while (set.contains(++i)) t++;
            max=Math.max(t,max);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15