LeetCode 热题100——128.最长连续序列

题目给定一个未排序的整数数组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提示0 nums.length 10^5-10^9 nums[i] 10^9答案1.易想到排序但是本题是不能排序的因为排序的时间复杂度是 O(nlogn)不符合题目 O(n) 的要求。class Solution { public: int longestConsecutive(vectorint nums) { if (nums.empty()) return 0; sort(nums.begin(),nums.end()); int maxlen1; int curlen1; for(int i1;inums.size();i){ if (nums[i]nums[i-1]) continue; else if(nums[i]nums[i-1]1){ curlen; } else{ maxlenmax(maxlen,curlen); curlen1; } } maxlen max(maxlen, curlen);//一定要写这句 return maxlen; } };正确答案class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint num_set(nums.begin(),nums.end());//设置为set去重 int maxlen0; for(int x:num_set){ if(!num_set.count(x-1)){// 如果x-1不在集合中说明x是某个连续序列的起点 int curNumx; int curlen1; while(num_set.count(curNum1)){//从x开始向后查找连续的数字 curNum; curlen; } maxlenmax(maxlen,curlen); } } return maxlen; } };举例演示nums [100, 4, 200, 1, 3, 2]1. 构建哈希集合遍历原数组将所有数字插入 unordered_set重复元素只保留一个。得到集合 num_set {100, 4, 200, 1, 3, 2}。2. 遍历集合寻找最长连续序列1处理 num 100num_set.count(99) → false所以 100 是起点。curNum 100curlen 1。while 循环检查 curNum1 101 是否在集合中false循环结束。当前序列长度 1maxlen max(0, 1) 1。2处理 num 4num_set.count(3) → true因为 3 在集合中所以 4 不是起点直接跳过。3处理 num 200num_set.count(199) → false200 是起点。curNum 200curlen 1。while检查 201 不存在结束。长度 1maxlen max(1, 1) 1。4处理 num 1num_set.count(0) → false1 是起点。curNum 1curlen 1。while 循环检查 2 在集合中 → curNum 2curlen 2检查 3 在集合中 → curNum 3curlen 3检查 4 在集合中 → curNum 4curlen 4检查 5 不在集合中 → 退出循环curNum 4maxlen max(1, 4) 4。5处理 num 3num_set.count(2) → true3 不是起点跳过。6处理 num 2num_set.count(1) → true2 不是起点跳过。3. 返回结果最终 maxlen 4对应连续序列 [1,2,3,4]。要点通过if (!num_set.count(num - 1))筛选出每个连续序列的最小元素起点。从起点开始用 while 循环不断查找下一个连续数统计序列长度。利用哈希集合的快速查找避免排序的 O(nlogn)开销实现O(n)时间复杂度