最长连续序列
# 📃 题目描述
题目链接:128. 最长连续序列 (opens new window)
# 🔔 解题思路
哈希表,每次搜索一个数搜完一个连续段,后面再遇到连续段中的直接跳过
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
// 记录最长连续序列的长度
int res = 1;
for (int i = 0; i < nums.length; i ++) {
// 以 cur 为起点的连续最长序列
int cur = nums[i];
// 记录以 cur 为起点的连续序列的长度
int len = 1;
// 如果 set 中包含了 num - 1,那么最长连续序列一定不是以 num 开头,最起码也是以 num - 1 开头
if (!set.contains(cur - 1)) {
while (set.contains(cur + 1)) {
cur ++;
len ++;
}
res = Math.max(len, res);
}
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10