longestConsecutiveSequence

128. 最长连续序列

分析

使用哈希集合 (unordered_set)：
- 首先将数组中的所有元素存入一个哈希集合 s 中，便于快速判断某个数字是否存在
遍历数组，寻找序列起点：
- 对于每个数字 start，如果 start - 1 不存在于集合中，说明它是某个连续序列的起点
- 从这个起点开始，逐步检查 start + 1, start + 2, … 是否存在于集合中，计算连续序列的长度
优化：删除已访问元素：
- 在遍历过程中，一旦某个数字被处理，可以从集合中删除，避免后续重复处理
更新结果：
- 记录所有连续序列的最大长度

时间复杂度

构建哈希集合：O(n) ，其中 n 是数组长度
遍历数组：
- 每个元素最多被访问两次（一次作为序列起点，一次作为序列中元素）
- 总复杂度为 O(n)

总时间复杂度为 O(n)

空间复杂度

使用了一个哈希集合存储数组中的所有元素，空间复杂度为 O(n)

C++代码

 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
30
31
32
33


class Solution {
public:
    int longestConsecutive(std::vector<int>& nums)
    {
        std::unordered_set<int> s; // 哈希集合存储所有数字
        for (int num : nums)
            s.insert(num);

        int res = 0; // 记录最长连续序列的长度

        for (int start : nums)
        {
            // 如果 start 是序列的起点（前一个数字不存在）
            if (s.count(start) && !s.count(start - 1))
            {
                int end = start; // 初始化序列的起点
                s.erase(end);    // 移除起点，避免重复处理

                // 找到当前序列的结尾
                while (s.count(end + 1))
                {
                    end += 1;
                    s.erase(end); // 同样移除，优化后续查询
                }

                // 更新最长长度
                res = std::max(res, end - start + 1);
            }
        }

        return res;
    }
};