解法一：排序
分析：
如果这个序列是个有序的序列，那么找到最长连续序列就比较简单，遍历一下这个数组，并做一些处理即可。
代码：
int longestConsecutive_sort(vector<int>& nums) {
if(nums.size()==0) return 0;
sort(nums.begin(),nums.end());
int maxLen = 1, curLen = 1, lastNum = nums[0];
for(int i=1; i<nums.size(); i++) {
cout<<nums[i];
if(nums[i] == lastNum) continue;
else if(nums[i] == lastNum + 1) curLen++;
else { //连不上了
maxLen = max(maxLen, curLen);
curLen = 1;
}
lastNum = nums[i];
}
maxLen = max(maxLen,curLen);
return maxLen;
}
解法二：集合
分析：
先将数组中所有的数存入集合。（利用集合O(1)的查找效率，快速判断集合中是否有某个数的下一个数字）
然后遍历数组中所有的数num：
- 看num+1在不在集合中，如果在，再看num+2在不在集合中......,一直找到num+k。
- 每找到一个，就将num作为左边界的连续序列长度+1，直到num+k不在集合中，即num+k不在数组中，停止当前num的处理，更新最大长度，处理数组中的下一个元素。
举例：数组为【2 4 5 7 3】，先把五个数都存在集合中，然后遍历数组，假如num为2，当前的序列长度就是1，然后取集合中找有没有3，有的话序列长度就+1，然后找4，找5，最后找不到6，则以2为左边界的连续序列长度为4，即【2 3 4 5】。
注意：我们可以看到，当2处理完后，下一个处理的就是4，最后处理结果是以4为左边界的连续序列长度为2（【4 5】），但是我们可以发现，4在处理2的时候已经处理过了，这个计算就没有必要存在，所以我们可以采取一定的剪枝处理。
剪枝：当处理某一个数num时，先判断num-1在不在集合（数组）中，如果数组中有num-1的话，就跳过当前num的处理。
因为num的处理不仅占用时间，且计算的结果一定是无意义的，对num进行处理后的连续序列的长度如果为m，那m一定不是我们想要的最大长度，因为num-1是在数组中的，加上num-1后，连续序列长度就变为m+1，我们不知道m+1是不是最后的结果，但至少m一定不是最后的最大长度，所以当存在num-1时，num的处理就被跳过。
代码：
int longestConsecutive_set(vector<int>& nums) {
unordered_set<int> num_set;
for (const int& num : nums) {
num_set.insert(num); //构建哈希表（集合，unordered_set内部实现为哈希表）
}
int longestStreak = 0;
for (const int& num : num_set) { //遍历集合
//判断num-1在不在，防止重复计数。如：对于4，如果集合中有3，则跳过，因为在处理3的时候，会紧接着处理4及4以后的数，避免重复的操作
if (!num_set.count(num - 1)) {
int currentNum = num; //当前处理的数
int currentStreak = 1;
while (num_set.count(currentNum + 1)) { //在哈希表中，查找时间为O(1)
currentNum += 1;
currentStreak += 1;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
解法三：哈希表
分析：
设置一个哈希表，存储的键值对表示如下：
- key：某一个数
- value：在当前已读取的数字中
- 该数作为边界时，其所处的最长连续序列的长度。（为了方便描述，我们定义当该数是边界时，哈希表的值称为【边界最大值】）
- 当该数非边界时，其value无意义。（硬说找到一个意义的话，就是该数上一次作为边界的时候，当时该数所在的最长连续序列的长度）
这样的话，我们遍历整个数组，当前处理某一个数
num：
如果
num不在哈希表中，即还没有读取过：
首先将
num自己看做一个只有自己，长度为1 的连续序列，并将其【边界最大值】设为1。然后在哈希表中查找，看
num-1和num+1是否在哈希表中：
如果
num-1不在，说明num的左边没有需要合并的序列，num需要作为左边界.如果
num+1不在，说明num的右边没有需要合并的序列，num需要作为右边界.如果
num-1或num+1在哈希表中，说明其已经被访问过，且哈希表中存的值，是该数的【边界最大值】（原因：num-1或num+1要么未被访问，要么作为一个序列的边界，不可能是被访问过的非边界元素）假如当前查找到
num-1在哈希表中，值为4
这就说明，num左边有一个长度为4的序列可以合并，我们就可以将其合并，并更新【边界最大值】，只需要更新新合并后的这个更长的连续序列的两个边界的【边界最大值】即可。如果
num已经在哈希表中，直接跳过，访问下一个元素。
具体实现：
遍历数组，如果num已经访问，则跳过；如果未被访问，进行下面的处理：
（假如当前已经读取过的数组组成的序列为：【 2 3 4】 【7 8 】，当前num为5）
- 先假设num两边都没有可以合并的序列，哈希表中插入<num,1>；
- 查看num左边可以合并的连续序列的长度
left_total_length：即查找哈希表中 5-1 的值，如果未找到，说明左边可合并长度为0。（上例中left_total_length为3）- 查看num右边可以合并的连续序列的长度
right_total_length：即查找哈希表中 5+1 的值，如果未找到，说明右边可合并长度为0。（上例中right_total_length为0）- 计算合并后的连续序列总长度：total_length = 左 + 1 + 右 = 3 + 1 + 0 =4。表示合并后序列长度为4，即【2 3 4 5】
- 更新
num-left_total_length和num-right_total_length在哈希表中的值为total_length，当right_total_length为0时，就是num作为右边界，即更新num的【边界最大值】
代码：
int longestConsecutive_hashset(vector<int>& nums) {
int res = 0;
int n=nums.size();
//表示该数 作为边界时的最长连续数组 的长度，
//当该数非边界时，其值无意义（或者说是其上一次作为边界时，当时其所在最长连续数组的长度）
//如：对于1，1的值为1；对于1234,1和4的值为4, 23的值取决于原数组的顺序，顺序不同，其值不同
unordered_map<int,int> count_map;
for(int num : nums) {
//不用考虑 非边界数字 的值 的影响，因为其如果不是边界，表示已经读取到它左边或右边的数字，并将它们作为了边界，
//对于距离边界最近 的非边界元素，也就是边界旁边的元素，这个时候边界也已经入表，已经没有别的情况需要考虑非边界的数值了
if(count_map.count(num)==0) {
//获取左右挨着的两个数，获取他们当前最长连续数组的长度
int left_total_length = count_map.count(num-1)!=0?count_map[num-1]:0; //c++中取某个key的value，如果没有就是0
int right_total_length = count_map.count(num+1)!=0?count_map[num+1]:0;;
//将当前读取数字入表，表示已经处理过该数字，这个值无所谓，是多少都行，
//因为如果num不是边界，左右数都已经入表，那以后再也用不到num的值，如果是边界，在下面更新操作中也会对num 的值进行更新
//处于科学一点的角度，取值为1
count_map[num] = 1;
//左 + 1 + 右
//例：1234 678 ，当前num为5，则左为4，右为6，都在表中，且4的值为4,6的值为3，则加上5后，总长度为4+1+3
int total_length = left_total_length+1+right_total_length;
//更新为最大
res = max(res , total_length);
//更新边界
//上例：1234 678，num为5，更新 [5-4]和[5+3] 即边界1和8的值为当前新的总长度
count_map[num-left_total_length] = total_length;
count_map[num+right_total_length] = total_length;
}
}
return res;
}
解法四：并查集
分析：
并查集基础知识在 数据结构：并查集
思路：
- 初始状态：所有元素 各自组成 集合，集合中只有自己一个元素
- 第一次遍历：将
num所在的集合 合并到num+1所在的集合- 如果
num+1存在，则合并，以num+1所在集合的根节点为合并后的根。
- 在并查集中的根节点，就代表当前集合中的最大元素
- 在本题的背景下，并查集中的根节点表示的是一个连续序列的右边界
- 举例：此时存在两个集合【1 2 3】【4 5】，此时遍历到num为3，即将3所在集合合并到4所在集合，集合【123】的father为3，【45】的father为5，合并后5为两个集合的新father。
- 在算法中，可以利用一个循环，将上面【123】的father都改为新根5，避免后续寻找根节点时，层次过深。
- 如果
num+1不存在，则跳过。- 第二次遍历：记录所有人与其father的距离，即与其所处连续序列右边界的距离
- 距离 = 右边界 - 当前元素 +1
代码：
class UnionFind {
private:
unordered_map<int,int> father;
public:
void init(vector<int> nums) {
for(int i = 0; i<nums.size(); i++) {
father.emplace(nums[i],nums[i]);
}
}
int find(int x) {
if(father.count(x) == 0) return INT_MAX;
//原本并查集中，如果没有找到father，返回NULL
//但是 C中 0==NULL，如果一个元素的father是0，也会被认为没有找到
//进而题中元素的范围只在-10^9 <= nums[i] <= 10^9 之间，所以，在没有找到father的时候，返回INT_MAX代替NULL
//递归的向上找father
int root = x;
while(root != father[root]) root = father[root];
//扁平化处理：从x到father，路径上所有的结点的father都改为整个集合的father，即root
while(x != father[x]) {
int cur = x;
x = father[x];
// father.emplace(cur,root); //emplace 插入时，key存在则不变，就是这个地方导致超时
father[cur] = root;
}
return root;
}
void merge_union(int x, int y) {
//y合并到x内，即x的根节点作为合并后的总根
x = find(x);
y = find(y);
if(x == y) return;
if(x==INT_MAX || y==INT_MAX) return;
father[y] = x;
}
void print_ufset() {
for(unordered_map<int,int>::iterator it=father.begin(); it!=father.end(); it++)
cout<<"num: "<<it->first<<" father: "<< it->second<<endl;
}
};
int longestConsecutive_unionfind(vector<int>& nums) {
if(nums.size()==0) return 0;
UnionFind uf;
uf.init(nums);
for(int num:nums){
uf.merge_union(num+1,num); //num的集合 合并到num+1 的集合中
}
int maxLen = 1;
for(int num:nums){
maxLen = max(maxLen , uf.find(num) - num +1);
}
return maxLen;
}
原文：https://www.cnblogs.com/kyrieliu/p/leetcode128.html