最长连续序列：hash与并查集写法

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

设计并实现时间复杂度为 O(n) 的算法解决此问题。

样例

输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是[1, 2, 3, 4]。它的长度为4。

题解

题目要求时间复杂度为$O(n)$，那么肯定不能排序，因为排序起码有$O(nlogn)$的复杂度。

下面我们通过两个角度来解决这道题：

1.哈希

我们先分析一个显然的暴力解法：先把所有数存到一个哈希集合中，然后双重循环遍历，判断其是否匹配。

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s;
    for(int x:nums) s.insert(x);
    int ans=0;
    for(int x:s){
        int l=1; //表示当前序列长度
        int n=x+1; //表示当前的数
        while(s.find(n)!=s.end()){
            l++;
            n++;
        }
        ans=max(ans,l);
    }
    return ans;
}

但是这样的时间复杂度太高，我们仔细分析可以发现原因是外层循环做了很多不必要的枚举。我们可以这样进行优化：每次都判断这个数x的前驱x-1存不存在，如果存在那么我们接下来枚举的肯定不是最长的序列，所以我们每次都需要枚举不存在前驱的数即可。

代码CPP · 21 行

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s;
        for(int x:nums) s.insert(x);
        int ans=0;
        for(int x:s){
            if(s.find(x-1)==s.end()){
                int l=1;
                int n=x+1;
                while(s.find(n)!=s.end()){
                    l++;
                    n++;
                }
                ans=max(ans,l);
            }
            
        }
        return ans;
    }
};

2.并查集

将连续的数字作为一个集合。那么扫描到一个数字，只要将它和它的下一个数字（假如存在）Union在一个集合即可。同时更新这个集合的元素个数。同时更新当前最长记录。

代码CPP · 31 行

class Solution {
public:
    unordered_map<int, int> father;
    unordered_map<int, int> cnt;
    int findFather(int x) {
        if (x == father[x]) return x;
        return father[x] = findFather(father[x]);
    }
    void Union(int x, int y) {
        int fx = findFather(x);
        int fy = findFather(y);
        if (fx != fy) {
            father[fx]=fy;
            cnt[fy]+=cnt[fx];
        }
    }
    int longestConsecutive(vector<int>& nums) {
        for(int x:nums){
            father[x]=x;
            cnt[x]=1;
        }
        int ans=0;
        for(int x:nums){
            if(father.find(x+1)!=father.end()){
                Union(x,x+1);
                ans=max(ans,cnt[findFather(x)]);
            }
        }
        return ans;
    }
};

这里用了一个cnt来记录集合元素数，因为如果最后再计算时间复杂度会超出。