【每日算法Day 6】最长连续序列
Wallace Xu 2020-06-06 哈希表
# 题目链接
LeetCode 128. 最长连续序列 (opens new window)
# 题目描述
给定一个未排序的整数数组，找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。
# 示例
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
1
2
3
2
3
# 解题思路
拿到题目一开始的想法是先排序再遍历一次，相邻的数如果递增则当前长度加1，否则最大长度取其和当前长度的最大值，并重置当前长度。但该做法时间复杂度为O(nlogn)+O(n)=O(nlogn)，不满足要求。想要O(n)则需要用空间换时间。则可将数组元素存入HashSet中以实现O(1)的查询时间，接下来再遍历数组，如果nums[i]+1存在，则持续查询并增加计数。但为避免重复查询，在此之前可加一判断如果nums[i]-1不存在才执行该查询。
public int longestConsecutive(int[] nums) {
Set<Integer> set=new HashSet<>();
for(int n:nums){
set.add(n);
}
int maxLen=0;
for(int n:nums){
if(!set.contains(n-1)){
int currentLen=1;
while(set.contains(++n)){
currentLen++;
}
maxLen=Math.max(maxLen,currentLen);
}
}
return maxLen;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 总结
此题还有使用并查集和动态规划的解法，这两天在忙着修改开题报告的终稿，后面再来补上。