C++零基础LeetCode热题100- 128.最长连续序列

题目描述

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

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

思路

常规的思路可能是排序后遍历，找到最长的连续段。这样的话，时间复杂度是O(n log n)，但题目要求O(n)，所以这种方法不可行。

那O(n)的算法就需要用哈希表了。

可以先把所有数字存入一个哈希集合中，这样可以快速查询某个数是否存在。然后遍历数组中的每个数，对于每个数，如果它的前一个数（num-1）不在集合中，那么就以这个数为起点，开始向后查找连续的数，比如num+1、num+2等等，直到找不到为止。

这样每个连续序列只会被处理一次，因为只有当当前数是序列的起点时才会进行遍历。

例如，假设数组中有4，那么如果3存在的话，4就不是起点，所以不会被处理。只有当处理到1的时候，因为没有0存在，所以开始从1向上找，得到1、2、3、4，长度为4。这样可以确保每个元素最多被访问两次（一次是放入集合，另一次是在查找序列时），因此时间复杂度是O(n)。

步骤

1. 将数组中的所有元素存入一个哈希集合，查询时间O(1)。

2. 初始化最长长度max_length为0。

3. 遍历数组中的每一个元素num：

   a. 如果num-1不在集合中，那么当前num可能是一个连续序列的起点。

   b. 然后从num开始，逐步检查num+1、num+2是否在集合中，直到找不到为止。

   c. 计算当前连续序列的长度，并更新max_length。

4. 返回max_length。

每个元素最多被访问两次，所以总的时间复杂度是O(n)。

实现代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
    // 创建哈希集合，存储所有数字，用于O(1)时间复杂度的存在性检查
    unordered_set<int> num_set(nums.begin(), nums.end());
    int max_len = 0; // 记录最长连续序列的长度

    // 遍历数组中的每个数字
    for (int num : nums) {
        // 如果当前数字的前一个数不在集合中，说明当前数字可能是一个连续序列的起点
        if (num_set.find(num - 1) == num_set.end()) {
            int current_num = num; 
            int current_len = 1;   // 当前连续序列的长度

            // 向后查找连续的数字，直到找不到下一个数为止
            while (num_set.find(current_num + 1) != num_set.end()) {
                current_num++; // 移动到下一个数字
                current_len++; // 增加当前序列长度
            }

            // 更新最大长度
            max_len = max(max_len, current_len);
        }
    }

    return max_len;
}
};

代码详解

unordered_set<int> num_set(nums.begin(), nums.end()) 将数组 nums 中的所有元素复制到一个哈希集合 num_set 中，用于快速构建一个哈希集合（HashSet）

nums 是一个 vector<int> 数组

nums.begin() 返回指向数组第一个元素的迭代器（指针）

nums.end() 返回指向数组末尾（最后一个元素的下一个位置）的迭代器

合起来表示将 nums 的全部元素作为输入范围。

unordered_set 的构造函数接受两个迭代器（ begin 和 end ），将范围内的所有元素插入集合。

且插入时会 自动去重 ：例如，如果 nums 中有多个 5，集合中只会保留一个 5。

有小白可能把 unordered_set 和 unordered_map 弄混淆，前者是哈希集合，后者是哈希表。以下是区分：

在本题中， unordered_set<int> 是最优选择，而 unordered_map<int, int> 既不必要，又浪费资源。

for (int num : nums) 范围 for 循环，遍历容器（如数组、vector、list 等）中的每一个元素，可代替 for (int i = 0; i < nums.size(); ++i)

int num ：定义一个临时变量 num ，类型为 int （与容器元素类型一致）。

nums ：被遍历的容器（如 vector<int> 或数组）。

循环过程：每次迭代时，将容器中的一个元素赋值给 num ，并执行循环体内的代码。

if (num_set.find(num - 1) == num_set.end())

end() 是 unordered_set 的成员函数，返回指向集合末尾的迭代器（表示 无效 位置）

如果 find() 返回的迭代器等于 end() ，说明未找到 num - 1

提交结果

注意

for (int num : nums) 范围 for 循环，可代替 for (int i = 0; i < nums.size(); ++i)

范围 for 循环本质上是 语法糖，编译器会将其转换为传统的迭代器循环

2.外层循环的遍历对象一定要是哈希集合 num_set 而不能是原数组 nums ，否则会出现：

原因：

当输入数组包含 大量重复元素 时，外层循环次数会远高于实际需要处理的元素数量。

例如：输入 nums = [0, 0, 0, 0, …]（含无数个元素）。

哈希集合 num_set 中实际只有 1 个元素 0，外层循环仍会执行 1e5 次，但每次处理的逻辑相同，浪费大量时间。

因此：