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(vectorint nums) { unordered_setint num_set(nums.begin(),nums.end()); vectorint begin_num; for(int num:num_set){ if(num_set.count(num-1)0num_set.count(num1)!0){ begin_num.emplace_back(num); } } int len; if(nums.empty()){len0;} else{len1;} for(int num:begin_num){ int len11; while(num_set.count(num1)){ len1; num; } if(len1len){lenlen1;} } return len; } };代码在空间和逻辑上可以改进省去begin_num无需额外数组存起点。遍历num_set时确认是起点后直接计算长度并更新最大值即可。简化判断无需判断num 1是否存在孤立点长度为 1 不影响结果。省略特判将最大长度初始值设为0用max更新空数组自然返回0无需特判nums.empty()。改进后代码class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint num_set(nums.begin(),nums.end()); int max_len0; for(int num:num_set){ if(num_set.count(num-1)0){ int cnum num; int len11; while(num_set.count(cnum1)){ len1; cnum; } max_len max(max_len,len1); } } return max_len; } };