每日一题一一Leetcode128.-最长连续序列-力扣
目录
每日一题一一Leetcode128. 最长连续序列 - 力扣
每日一题一一Leetcode128. 最长连续序列 - 力扣
作者：blue
时间：2025.3.14
本题的要求是：给定一个未排序的整数数组
nums
，找出其中数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
本题用排序加遍历的方法非常容易解决，但是算法的效率太低。
本题正真的解题思路如下，
首先，数组中是有可能出现重复的数字，但是重复的数字其实并不影响我们找数字连续的最长序列，因为再多相同的也只能算一个长度，所以，我们可以先对数组进行一个 去重 （放进集合中）。
然后我们遍历这个去重后的集合，每次遍历到一个数（在这里我称之为num），我们就去询问set，“num-1在不在集合中？”
问这个的目的是判断当前这个num有没有资格作为数字连续序列的开头，你想，如果num-1都存在，那么你以num为头去找一个数字连续序列，那肯定不会是最长的。
好，那么如果num-1不存在，那么说明num有资格，作为数字连续序列的开头，我们就不断询问num+1，num+2，num+3，……在不在集合中，看看什么时候停下来，然后，维护最长序列的长度即可。
C++代码：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int ans=0;
unordered_set<int> us(nums.begin(),nums.end());
for(int num:us){
if(!us.contains(num-1)){
int cur_num = num;
int cur_len = 1;
while(us.contains(cur_num+1)){
cur_num+=1;
cur_len+=1;
}
ans = max(cur_len,ans);
}
}
return ans;
}
};Java代码
import java.util.HashSet;
public class Day03_demo128 {
public static void main(String[] args) {
int x = longestConsecutive(new int[] {0,3,7,2,5,8,4,6,0,1});
System.out.println(x);
}
public static int longestConsecutive(int[] nums) {
int res = 0;
HashSet<Integer> hashSet = new HashSet<>();
for (int num : nums) {
hashSet.add(num);
}
for (Integer num : hashSet) {
if(!hashSet.contains(num-1)){
int curNum = num;
int curLen = 1;
while(hashSet.contains(curNum+1)){
curNum+=1;
curLen+=1;
}
res = Math.max(curLen,res);
}
}
return res;
}
}