最长连续序列

题目描述

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

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

数据样例

示例 1：

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

示例 2：

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

提示：

  • $0 \leq nums.length \leq 10 ^ 5$
  • $-10 ^ 9 \leq nums[i] \leq 10 ^ 9$

哈希表 - $O(N)$

哈希表

对于给定数组中的每一个数 $x$，我们依次来看：$x + 1, x + 2, …$ 是否存在。

假设我们找到最大的 $y$ 使得 $x, x + 1, …, x + y$ 都在数组中。那么 以 $x$ 开头的连续的元素最多就有 $y$ 个

因此：可以 依次枚举数组中的元素 作为 $x$，依次枚举 $x + 1, x + 2, …$ 找到最大的 $y$ 即可

  • 每次判断一个数是否在数组中，如果直接枚举，那么每次寻找 $y$ 需要 $O(N)$ 遍历一遍数组

因此可以使用 哈希表 来判断元素是否存在于数组中，哈希表每次查询时间复杂度为 $O(1)$

优化：

  • 如果某个数之前已经被枚举过了，也就是如果其已经和前面某个数构成连续序列了，则跳过。
  • 可以直接枚举哈希表，因为哈希表中会将元素去重，重复元素可以跳过

时间复杂度 - $O(N)$

  • 每个元素最多被遍历过两次，一次是枚举到当前元素，另外一次是可能组成连续序列
  • 枚举数组中的所有元素 $O(N)$，每次查询哈希表复杂度为 $O(1)$，因此整体时间复杂度为 $O(N)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func longestConsecutive(nums []int) int {
    // 定义一个哈希表，记录数组中的元素
    res, S := 0, map[int]bool{}
    for _, key := range nums { S[key] = true }
    // 优化2：通过枚举哈希表来枚举数组中每个去重后的元素
    for key := range S {
        // 优化1：如果 key - 1 出现过，说明当前数已经被枚举过了，跳过
        if _, ok := S[key - 1]; !ok {
            cur, len := key, 1
            // 寻找最长的连续序列长度
            for S[cur + 1] { cur++; len++ }
            res = max(res, len)
        }
    }
    return res
}

func max(a, b int) int { if a < b {return b}; return a}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    unordered_set<int> S;

    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) S.insert(nums[i]);
        int res = 0;
        for (auto cur : S) {
            if (!S.count(cur - 1)) {
                int len = 1;
                while (S.count(cur + 1)) ++cur, ++len;
                res = max(res, len);
            }
        }
        return res;
    }
};