解法一：DFS

1、思路

• 用一个哈希set来存放所有的数字，每个循环用DFS找与之相邻的数字，累加相邻数字的个数，同时从哈希set中剔除这些数字；

• 时间复杂度为 $O(N)$ ， 空间复杂度为 $O(N)$ ，因为递归要压栈。

2、代码

class Solution {
public:
    int dfs(unordered_set<int>& hash, int num)
    {
        if (hash.find(num) == hash.end()) return 0;

        hash.erase(num);

        return dfs(hash, num + 1) + dfs(hash, num - 1) + 1;
    }

    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;

        unordered_set<int> hash;
        for (int& num : nums)
        {
            hash.insert(num);
        }

        int res = 0;
        for (int i = 0; i < nums.size(); ++ i)
        {
            if (hash.find(nums[i]) != hash.end())
            {
                res = max(res, dfs(hash, nums[i]));
            }
        }

        return res;
    }
};

解法二：BFS

1、思路

同上。

2、代码

class Solution {
public:
    int bfs(unordered_set<int>& hash, int num)
    {
        queue<int> q;
        q.push(num);
        int maxLen = 0;

        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            hash.erase(cur);
            maxLen ++ ;

            if (hash.find(cur + 1) != hash.end())
            {
                q.push(cur + 1);
            }

            if (hash.find(cur - 1) != hash.end())
            {
                q.push(cur - 1);
            }
        }

        return maxLen;
    }

    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;

        unordered_set<int> hash;
        for (int& num : nums)
        {
            hash.insert(num);
        }

        int res = 0;
        for (int i = 0; i < nums.size(); ++ i)
        {
            if (hash.find(nums[i]) != hash.end())
            {
                res = max(res, bfs(hash, nums[i]));
            }
        }

        return res;
    }
};

解法三：并查集

1、思路

• 对于每个整数num，若存在num + 1和num - 1，当它们在不同子集中时，将它们所在的子集用makeUnion函数合并，并更新合并后子集元素的数目；

• 时间复杂度为 $O(N)$， 空间复杂度为 $O(N)$ 。

2、代码

class Solution {
public:
    int findFather(unordered_map<int, int>& fathers, int i) //找根节点
    {
        if (fathers[i] != i)
        {
            fathers[i] = findFather(fathers, fathers[i]);
        }

        return fathers[i];
    }

    void makeUnion(unordered_map<int, int>& fathers, unordered_map<int, int>& counts,
                    int i, int j)
    {
        int fatherOfI = findFather(fathers, i);
        int fatherOfJ = findFather(fathers, j);

        if (fatherOfI != fatherOfJ)
        {
            fathers[fatherOfI] = fatherOfJ;             //两子集合并

            int countOfI = counts[fatherOfI];
            int countOfJ = counts[fatherOfJ];
            counts[fatherOfJ] = countOfI + countOfJ;    //更新两子集合并后的大小
        }
    }

    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> fathers;    //数字与其对应的根节点
        unordered_map<int, int> counts;     //数字与其所在子集的大小
        unordered_set<int> all;             //存放所有的数字

        for (int& num : nums)
        {
            fathers[num] = num;             //初始化：每个数字的根节点是它自己
            counts[num] = 1;                //子集大小为 1
            all.insert(num);
        }

        for (int& num : nums)
        {
            //集合中存在 num + 1 或 num - 1，则合并
            if (all.find(num + 1) != all.end())
            {
                makeUnion(fathers, counts, num, num + 1);
            }

            if (all.find(num - 1) != all.end())
            {
                makeUnion(fathers, counts, num, num - 1);
            }
        }

        int res = 0;
        for (pair<int, int> count : counts) //统计最大连续序列的长度
        {
            res = max(res, count.second);
        }

        return res;
    }
};