题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。
示例 1：

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

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• $0<=nums.length<=10^5$
• $-10^9<=nums[i]<=10^9$

题解

解法一：哈希表

【思路】

如果给定的数组中存在连续序列，则要找到最长的连续序列，就要从连续序列的第一个数开始，即如果数组中存在连续序列 $x,x+1,x+2,...,x+y$，那么应该从 $x$ 开始计算这个连续序列，而不是从 $x+i$ ($i>0$) 开始计算。为了避免重复计算，所以遇到不是连续序列开头的数字就直接跳过。
跳过的判断方法：判断 $x-1$ 是否存在，如果存在，则 $x$ 不是连续序列的开头，直接跳过。

【代码】

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hashTable;
        for (const int &num : nums) hashTable.insert(num);
        int ans = 0;
        for (const int &num : nums) {
            if (!hashTable.count(num - 1)) { //确定num是否为连续序列的开头元素
                int len = 1;
                int currentNum = num;
                while (hashTable.count(currentNum + 1)) { //查找num + i是否存在，记录能达到的最大长度
                    len++;
                    currentNum++;
                }
                ans = max(len, ans);
            }
        }
        return ans;
    }
};

解法二：并查集

【思路】

• 利用哈希表存储 father，father[i] 表示从 $i$ 开始能达到的连续序列的最大数 。
• find 函数中通过并查集的路径压缩算法递归地查找 $i$ 能到达的最远位置。

【代码】

class Solution {
public:
    unordered_map<int, int> father;
    //路径压缩算法:时间复杂度趋近于O(1)
    int find(int x) {
        return father.count(x) ? father[x] = find(father[x]) : x;
    }

    int longestConsecutive(vector<int>& nums) {
        //初始化，使得映射关系为num -> num + 1
        for (const int &num : nums) { 
            father[num] = num + 1;
        }
        int ans = 0;
        for (const int &num : nums) {
            if (!father.count(num - 1)) { //找到连续序列的第一个元素
                int maxNum = find(num + 1);
                ans = max(ans, maxNum - num);
            } 
        }
        return ans;
    }
};