题目描述

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 $O(n)$。

样例

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

算法1

(暴力枚举) $O(n^3)$

我们先想暴力的做法怎么做：我们可以枚举数组中的每个数作为一个连续序列的起点，对于每个起点，我们找以它为起点的最长连续序列的长度。

时间复杂度

共有 $n$ 个起点，每次以该起点搜索时每次搜索后当前序列的长度都会加一，所以最多搜索 $n$ 次，每次最多需要 $O(n)$ 的时间，所以一共需要 $O(n^3)$ 的复杂度。这种做法会超时。

C++ 代码

class Solution {
public:
    bool find(vector<int>& nums, int n) {
        for (auto x : nums)
            if (x == n) return true;
        return false;
    }

    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            int cur = 1;
            while (find(nums, nums[i] + cur)) cur ++ ;
            res = max(res, cur);
        }
        return res;
    }
};

算法2

(哈希表) $O(n)$

显然在算法一中我们每次查找数组中是否包含某个数时需要耗费 $O(n)$ 时间扫描一遍数组来得到，这是不必要的，因为我们可以提前构造一个包含数组全部元素的哈希表，这样每次查询就只需要 $O(1)$ 的时间，总时间复杂度会降到 $O(n^2)$。虽然足以通过本题但还是不满足题目 $O(n)$ 的要求，下面我们进一步优化。

可以注意到对于每个连续序列比如1, 2, 3, 4，我们只需要枚举它的起点1就好了，对于剩下的2, 3, 4我们可以直接跳过。设一个数为x，那么当x - 1不存在的时候就说明它是某一个序列的起点。

时间复杂度

对于每个长度为n的序列，我们只会花费 $O(n)$ 的时间去枚举它，所以总时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:  
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash(nums.begin(), nums.end());
        int res = 0;
        for (int i = 0; i < nums.size(); i ++ ) {
            if (!hash.count(nums[i] - 1)) {
                int cur = 1;
                while (hash.count(nums[i] + cur)) cur ++ ;
                res = max(res, cur);
            }
        }
        return res;
    }
};

算法3

(排序) $O(n\log n)$

当然本题也可以用排序来做，将数组排完序后连续序列的数字就会排在一起，我们扫描一遍数组就可以得到最长的连续序列长度了。

这里有一些细节需要注意，当我们遇到相同数字时当前连续序列的长度并不会增长，所以我们在扫描的过程中还需要记录一下当前连续序列里重复数字的个数。

时间复杂度

排序需要的时间复杂度为 $O(n\log n)$，不过在实际运行中这种做法甚至比 $O(n)$ 的算法二还要快。

C++ 代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int res = 0;

        int i = 0, j = 0, dup = 0;
        for (; i < nums.size(); i ++ ) {
            if (i && nums[i] == nums[i - 1]) dup ++ ;
            else if (i && nums[i] != nums[i - 1] + 1) {
                res = max(res, i - j - dup);
                j = i;
                dup = 0;
            }
        }
        res = max(res, i - j - dup);

        return res;
    }
};

算法4

(哈希表) $O(n)$

我们可以开一个哈希表来记录每个点以及每个点所对应的区间的长度，这里只有区间端点的值才是真正的区间长度，而区间内部的的点的值仅起到记录该点出现过的意义。这样当我们遇到一个点x时，若之前遇见过我们直接跳过，若没出现过我们查找x - 1以及x + 1是否在哈希表中存在，若存在则它们一定都是区间的端点，因为点x是第一次遇见。之后我们可以更新区间端点的新长度值，同时维护我们的答案。

C++ 代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> hash;

        int res = 0;
        for (auto x : nums) {
            if (hash.count(x)) continue;
            hash[x] = 1;

            int left = 0, right = 0;
            if (hash.count(x - 1) && hash.count(x + 1)) {
                left = hash[x - 1], right = hash[x + 1];
                hash[x - left] = hash[x + right] = left + right + 1;
            } else if (hash.count(x - 1)) {
                left = hash[x - 1]; 
                hash[x - left] = hash[x] = left + 1;
            } else if (hash.count(x + 1)) {
                right = hash[x + 1];
                hash[x + right] = hash[x] = right + 1;
            } 

            res = max(res, left + right + 1);
        }

        return res;
    }
};

算法5

(并查集) $O(n)$

在本题的tag中还有并查集，下面我们看一下如何用并查集来做这道题。

如果我们把每个数都看成一个点，初始时它们的father都指向它们自己，每个数自己就是一个集合，集合的大小为1。那么当我们要插入一个点x时，我们可以利用并查集找到x - 1和x + 1所在的集合，然后将这两个集合与x合并，同时维护集合的大小。当我们遍历完整个数组做并查集后，我们扫描一遍集合的大小数组，就可以得到答案了。

由于这里输入的数据大小范围不固定，我们可以用哈希表unordered_map来当做传统并查集中的father数组，相当于我们可以用任意值来做索引而不像数组只能以下标来索引。

C++ 代码

class Solution {
public:
    unordered_map<int, int> f, cnt;

    int find(int x) {
        if (f[x] != x) f[x] = find(f[x]);
        return f[x];
    }

    void uni(int a, int b) {
        int x = find(a), y = find(b);
        if (x != y) f[x] = y, cnt[y] += cnt[x];
    }

    int longestConsecutive(vector<int>& nums) {
        for (auto x : nums) {
            if (!f.count(x)) f[x] = x, cnt[x] = 1;
            else continue;

            if (f.count(x - 1)) uni(x, x - 1);
            if (f.count(x + 1)) uni(x, x + 1);
        }
        int res = 0;
        for (auto p : cnt) res = max(res, p.second);
        return res;
    }
};