给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
> 方法一：双指针
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
sort(nums.begin(),nums.end());
unique(nums.begin(),nums.end());
int left,right;
left = 0;
right = 1;
int len = nums.size();
if(len <= 1) return len;
int res = 1;
int l = 1;
while(left < len && right < len){
if(nums[right - 1] + 1 == nums[right]){
right++;
}
else{
res = max(res,right - left);
left = right;
right++;
}
}
res = max(res,right - left);
return res;
}
};
> 方法二：哈希集合
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> st;
for(const auto&p:nums){
st.insert(p);
}
int ans = 0;
for(const auto&p:nums){
int cur = p;
if(!st.count(cur-1)){
while(st.count(cur+1)){
cur++;
}
}
ans = max(ans,cur-p+1);
}
return ans;
}
};
> 方法三：哈希表
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int,int> mp;
for(const auto&p:nums){
mp[p] = p;
}
int ans = 0;
for(const auto&p:nums){
if(!mp.count(p-1)){
int right = mp[p];
while(mp.count(right+1)){
right = mp[right + 1];
}
ans = max(ans,right-p+1);
}
}
return ans;
}
};
> 方法四：哈希表记录连续区间长度（动态规划）
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int,int> mp;
int ans = 0;
for(const auto&p:nums){
//当p第一次出现时
if(!mp.count(p)){
int left,right;
left = 0;
right = 0;
auto l = mp.find(p-1);
if(l != mp.end()) left = l->second;
auto r = mp.find(p+1);
if(r != mp.end()) right = r->second;
int cur_len = left + right + 1;
ans = max(cur_len,ans);
mp[p] = 1;
mp[p - left] = cur_len;
mp[p + right] = cur_len;
}
}
return ans;
}
};
> 方法五：并查集思想
class Solution {
public:
unordered_map<int,int> a,b;
int find(int x){
//并查集思想，路径压缩
return a.count(x)?a[x]=find(a[x]):x;
}
int longestConsecutive(vector<int>& nums) {
for(auto i:nums)
a[i]=i+1;
int ans=0;
for(auto i:nums){
int y=find(i+1);
ans=max(ans,y-i);
}
return ans;
}
};