最长连续序列

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)

示例:

1
2
3
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解法:
将数组放进set里面,然后找出第一个数,pre表示这个树的前一个,next表示后一个,最后返回next-pre+1就是最长连续序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class  {
public int longestConsecutive(int[] nums) {
if (nums==null||nums.length==0){
return 0;
}
int res=0;
Set<Integer> set=new HashSet<>();
for (int num:nums){
set.add(num);
}
for (int num:nums){
if (set.remove(num)){
int pre=num-1,next=num+1;
while (set.remove(pre)){--pre;}
while(set.remove(next)){++next;}
res=Math.max(res,next-pre-1);
}
}
return res;
}
}