Leetcode热题100_128.最长连续序列

题目要求

  • 给定一个未排序的整数数组 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

示例 3：
输入：nums = [1,0,1,2]
输出：3

哈希表

  • 对于数组中存在的连续序列，为了统计每个连续序列的长度，我们希望直接定位到每个连续序列的起点，从起点开始遍历每个连续序列，从而获得长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int groupAnagrams(int[] nums) {
        Set<Integer> set = new HashSet<>();
        // 将数组中元素添加到哈希表中，便于后续快速查找
        for(int num : nums) {
            set.add(num);
        }

        // 遍历set中的每个元素，寻找连续序列的起点
        int len = 0;
        int maxLen = 0;
        for(int num : set) {
            // 如果当前元素-1存在，说明该元素不是起点，跳过该元素
            if (set.contains(num - 1)) {
                continue;
            }

            // 从当前元素开始，向后寻找连续序列的长度
            len = 1;
            while (set.contains(++num)) {
                len++;
            }
            // 更新最长连续序列的长度
            maxLen = Math.max(maxLen, len);
        }

        return maxLen;
    }
}
  • 时间复杂度：
    • 将数组元素添加到哈希表中需要 O(n) 的时间。
    • 遍历哈希表中的每个元素需要 O(n) 的时间。
    • while循环在最坏的情况下可能需要执行n次。然而，由于集合查找操作的时间复杂度是O(1)，这个while循环并不会显著增加总体的时间复杂度。
    • 所以总体时间复杂度为 O(n)。
  • 空间复杂度：
    • 哈希表中存储了数组中的所有元素，空间复杂度为 O(n)。

关于时间复杂度

结论先给出来：时间复杂度是 O(n)。
不是 O(n²)，原因有点反直觉，但一拆开就很清晰。🧠

这里的 n 指的是 数组长度（或者说 set 中元素个数的数量级）。

先把代码拆成两个阶段看。

第一阶段是把数组放进 HashSet：

1
2
3
for(int num : nums) {
    set.add(num);
}

HashSet.add() 的平均复杂度是 O(1)（底层是哈希表）。
循环 n 次，所以这一段是：

1
O(n)

到这里没什么悬念。

真正让人疑惑的是第二部分：

1
2
3
4
5
6
7
8
9
10
for(int num : set) {
    if (set.contains(num - 1)) {
        continue;
    }

    len = 1;
    while (set.contains(++num)) {
        len++;
    }
}

乍一看会觉得：

1
2
3
外层 for: n
内层 while: 最坏 n
→ O(n²) ?

但实际不是，因为 while 不会被重复执行很多次。

关键逻辑是这一句：

1
if (set.contains(num - 1)) continue;

这句话的意思是：

只有连续序列的起点才会进入 while

例如：

1
set = {1,2,3,4,5}

遍历过程：

1
2
3
4
5
num=1  → 0 不存在 → 起点 → while 扫描 1,2,3,4,5
num=2  → 1 存在 → 跳过
num=3  → 2 存在 → 跳过
num=4  → 3 存在 → 跳过
num=5  → 4 存在 → 跳过

注意一个关键事实：

每个元素只会被 while 扫描一次。

while 访问的序列：

1
1 → 2 → 3 → 4 → 5

之后再遍历到 2,3,4,5 时：

1
直接 continue

不会再次进入 while。

从“元素被访问的次数”角度看更清晰：

每个数字最多经历：

  1. for 循环访问一次
  2. while 扩展访问一次

所以总访问次数是：

1
O(n) + O(n)

也就是：

1
O(n)

再看一个极端情况：

1
nums = [100,4,200,1,3,2]

set：

1
{1,2,3,4,100,200}

运行过程：

1
2
3
4
5
6
1 → while 扫描 1,2,3,4
2 → 跳过
3 → 跳过
4 → 跳过
100 → while 扫描 100
200 → while 扫描 200

所有 while 加起来访问：

1
1,2,3,4,100,200

还是 每个元素一次。

所以完整复杂度：

1
2
3
构建 set      O(n)
遍历 set      O(n)
while 扫描    O(n)

总复杂度：

1
O(n)

空间复杂度：

1
O(n)

（因为 HashSet 存了所有元素）