‍博主名称鱼子星_✅数据结构专栏【数据结构】✅算法竞赛专栏【算法竞赛】✅C系列专栏【C从零开始系列】128. 最长连续序列【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解题思路解法一排序去重将数组排好序后使用unique函数去重这样就可以保证升序的元素一直是相邻的然后直接遍历数组同时维护最长的连续即可 代码classSolution{public:intlongestConsecutive(vectorintnums){if(nums.size()0)return0;//排序去重sort(nums.begin(),nums.end());intcntunique(nums.begin(),nums.end())-nums.begin();//统计最大长度intret0;intt0;for(inti0;icnt-1;i){if(nums[i]nums[i1]-1){t;}else{retmax(ret,t1);t0;}}retmax(ret,t1);returnret;}};提交结果解法二哈希表先将数组所有的元素放入自动去重的哈希表中之后开始遍历原数组。遍历到i时刻就判断hash[nums[i] - 1]是否大于0如果不是大于0就代表当前元素是某个上升序列的开头。从这个元素的数值开始不断往后判断hash[nums[i] 1 * x]是否大于0当遇到0时代表序列结束更新最终结果即可。而如果hash[nums[i] - 1]等于0就直接跳过即可。LeetCode官方代码classSolution{public:intlongestConsecutive(vectorintnums){unordered_setintnum_set;for(constintnum:nums){num_set.insert(num);}intlongestStreak0;for(constintnum:num_set){if(!num_set.count(num-1)){intcurrentNumnum;intcurrentStreak1;while(num_set.count(currentNum1)){currentNum1;currentStreak1;}longestStreakmax(longestStreak,currentStreak);}}returnlongestStreak;}};提交结果