企业官网建设流程全解析

题目描述

128. 最长连续序列 - 力扣（LeetCode）

解题思路

这道题看到第一眼想法是用sort排序后直接遍历找最长序列，可惜sort排序时间复杂度为O(nlogn)，并不符合题目O(n)的要求。

之后考虑用到哈希表，把所有数字存入哈希集合实现 O (1) 查找，之后的这个思路很关键，就是想到只从连续序列的起点开始统计长度。判断条件是集合中不存在"当前数字-1"说明是序列开头，再循环向后查找连续数字，统计序列长度，更新全局最大值。每个元素只会被访问一次，整体时间复杂度就是O (n)。

代码如下：

class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> ust; // 全部放入哈希集合，O(n) for(auto it: nums) { ust.insert(it); } int ans=0; // 遍历集合 for(auto it = ust.begin();it != ust.end();it++) { // *it-1不在集合，说明当前元素是一段连续序列的起点 if(!ust.count(*it-1)) { int cnt=1; int tar=*it+1; // 不断往后找连续数字 while(ust.count(tar)) { cnt++; tar=tar+1; } ans=max(ans,cnt); } } return ans; } };

时间复杂度：O(n)，每个元素最多进入 while 循环一次

空间复杂度：O(n)，哈希集合存储全部数字

值得注意的是不要直接遍历原数组nums，有大量重复数字；遍历unordered_set自动去重，减少循环次数。