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; } };

代码在空间和逻辑上可以改进：

1. 省去begin_num：无需额外数组存起点。遍历num_set时，确认是起点后直接计算长度并更新最大值即可。
2. 简化判断：无需判断num + 1是否存在，孤立点长度为 1 不影响结果。
3. 省略特判：将最大长度初始值设为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; } };