LeetCode Hot 100(3.最长连续序列）
3.最长连续序列
题目
给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]输出：9
示例 3：
输入：nums = [1,0,1,2]输出：3
解法：利用num_set去重
代码
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> num_set(nums.begin(),nums.end()); vector<int> begin_num; for(int num:num_set){ if(num_set.count(num-1)==0&&num_set.count(num+1)!=0){ begin_num.emplace_back(num); } } int len; if(nums.empty()){len=0;} else{len=1;} for(int num:begin_num){ int len1=1; while(num_set.count(num+1)){ len1++; num++; } if(len1>len){len=len1;} } return len; } };代码在空间和逻辑上可以改进：
- 省去
begin_num：无需额外数组存起点。遍历num_set时，确认是起点后直接计算长度并更新最大值即可。 - 简化判断：无需判断
num + 1是否存在，孤立点长度为 1 不影响结果。 - 省略特判：将最大长度初始值设为
0，用max更新，空数组自然返回0，无需特判nums.empty()。
改进后代码
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> num_set(nums.begin(),nums.end()); int max_len=0; for(int num:num_set){ if(num_set.count(num-1)==0){ int cnum = num; int len1=1; while(num_set.count(cnum+1)){ len1++; cnum++; } max_len =max(max_len,len1); } } return max_len; } };