最长连续序列 | 秋招知识库

首先，本题是不能排序的，因为排序的时间复杂度是 $O (n \log n)$ ，不符合题目 $O (n)$ 的要求。

核心思路：对于 $nums$ 中的元素 $x$ ，以 $x$ 为起点，不断查找下一个数 $x + 1, x + 2, x + 3, \dots$ 是否在 $nums$ 中，同时统计连续序列的长度。

为了做到 $O (n)$ 时间复杂度，需要两个关键优化：

把 $nums$ 中的数都放入一个哈希集合中，这样可以 $O (1)$ 判断数字是否在 $nums$ 中。
如果 $x - 1$ 在哈希集合中，则不以 $x$ 为起点。为什么？因为以 $x - 1$ 为起点计算出的序列长度，一定比以 $x$ 为起点计算出的序列长度要长！这样可以避免大量重复计算。比如 $nums = [3, 2, 4, 5]$ ，从 $3$ 开始，我们可以找到 $3, 4, 5$ 这个连续序列；而从 $2$ 开始，我们可以找到 $2, 3, 4, 5$ 这个连续序列，一定比从 $3$ 开始的序列更长。

⚠注意：遍历元素的时候，要遍历哈希集合，而不是 $nums$ ！如果 $nums = [1, 1, 1, \dots, 1, 2, 3, 4, 5, \dots]$ （前一半都是 $1$ ），遍历 $nums$ 的做法会导致每个 $1$ 都跑一个 $O (n)$ 的循环，总的循环次数是 $O (n^{2})$ ，会超时。

Python 解法1C++ 解法1

python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        st = set(nums)  # 把 nums 转成哈希集合
        ans = 0
        for x in st:  # 遍历哈希集合
            if x - 1 in st:  # 如果 x 不是序列的起点，直接跳过
                continue
            # x 是序列的起点
            y = x + 1
            while y in st:  # 不断查找下一个数是否在哈希集合中
                y += 1
            # 循环结束后，y-1 是最后一个在哈希集合中的数
            ans = max(ans, y - x)  # 从 x 到 y-1 一共 y-x 个数
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end()); // 把 nums 转成哈希集合
        int ans = 0;
        for (int x : st) { // 遍历哈希集合
            if (st.contains(x - 1)) { // 如果 x 不是序列的起点，直接跳过
                continue;
            }
            // x 是序列的起点
            int y = x + 1;
            while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中
                y++;
            }
            // 循环结束后，y-1 是最后一个在哈希集合中的数
            ans = max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
        }
        return ans;
    }
};

小优化：设 $m$ 为 $nums$ 中的不同元素个数（即哈希集合的大小）。各个连续序列（链）是互相独立的，如果我们发现其中一条链的长度至少为 $\frac{m}{2}$ （长度乘 $2$ 大于等于 $m$ ），由于不可能还有一条长度大于 $\frac{m}{2}$ 的链（否则这两条链的长度之和就超过 $m$ 了），答案不会再增大，此时可以直接返回答案。

Python 解法3C++ 解法3

python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        st = set(nums)  # 把 nums 转成哈希集合
        m = len(st)

        ans = 0
        for x in st:  # 遍历哈希集合
            if x - 1 in st:  # 如果 x 不是序列的起点，直接跳过
                continue
            # x 是序列的起点
            y = x + 1
            while y in st:  # 不断查找下一个数是否在哈希集合中
                y += 1
            # 循环结束后，y-1 是最后一个在哈希集合中的数
            ans = max(ans, y - x)  # 从 x 到 y-1 一共 y-x 个数
            if ans * 2 >= m:  # ans 不可能变得更大
                break
        return ans

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end()); // 把 nums 转成哈希集合
        int ans = 0;
        for (int x : st) { // 遍历哈希集合
            if (st.contains(x - 1)) { // 如果 x 不是序列的起点，直接跳过
                continue;
            }
            // x 是序列的起点
            int y = x + 1;
            while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中
                y++;
            }
            // 循环结束后，y-1 是最后一个在哈希集合中的数
            ans = max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
            if (ans * 2 >= st.size()) {
                break;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。在二重循环中，每个元素至多遍历两次：在外层循环中遍历一次，在内层循环中遍历一次。所以二重循环的时间复杂度是 $O (n)$ 的。比如 $nums = [1, 2, 3, 4]$ ，其中 $2, 3, 4$ 不会进入内层循环，只有 $1$ 会进入内层循环。
空间复杂度： $O (m)$ 。其中 $m$ 是 $nums$ 中的不同元素个数。

相似题目

2007. 从双倍数组中还原原数组

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

相似题目 ​

分类题单 ​

复杂度分析

相似题目

分类题单