正文
leetcode 128. 最长连续子序列
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目描述：
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n) 。
示例:
输入：[100, 4, 200, 1, 3, 2]
输出：4
即最长的连续序列为 [1,2,3,4]
思路分析：
由于要求O(n)的复杂读，因此直接排序是不可行的。
这里用到的是并查集的思想。对于每一个数，去查小于1和大于1的数是否在序列中。通过迭代求解。
尽管在 for 循环中嵌套了一个 while 循环，时间复杂度看起来像是二次方级别的。但其实它是线性的算法。因为只有当 currentNum 遇到了一个序列的开始， while 循环才会被执行（也就是 currentNum-1 不在数组 nums 里）， while 循环在整个运行过程中只会被迭代 n 次。这意味着尽管看起来时间复杂度为 O(n⋅n) ，实际这个嵌套循环只会运行 O(n + n) =O(n) 次。所有的计算都是线性时间的，所以总的时间复杂度是 O(n)的。
代码：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.size()==)
return ;
int ans = ;
unordered_set<int> myset(nums.begin(), nums.end());
for(int i = ; i<nums.size(); i++)
{
if(myset.count(nums[i]-)==)
{
int x = nums[i]+;
while(myset.count(x))
{
x++;
}
ans = max(ans, x-nums[i]);
}
}
return ans;
}
};
