题目描述

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

代码详解

1.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<T>	存储单一类型的元素，快速判断存在性	unordered_set<int>	只需判断元素是否存在
unordered_map<K,V>	存储键值对，关联数据	unordered_map<string, int>	需要记录键的附加信息（如计数）

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

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

   int num：定义一个临时变量 num，类型为 int（与容器元素类型一致）。
   nums：被遍历的容器（如 vector<int> 或数组）。
   循环过程：每次迭代时，将容器中的一个元素赋值给 num，并执行循环体内的代码。

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

   end() 是 unordered_set 的成员函数，返回指向集合末尾的迭代器（表示无效位置）
   如果 find() 返回的迭代器等于 end()，说明未找到 num - 1

提交结果

注意

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 次，但每次处理的逻辑相同，浪费大量时间。

因此：

情况	外层循环次数	时间复杂度	适用场景
遍历原数组 nums	O(n)	O(n)	无重复元素
遍历哈希集合 num_set	O(m) (m ≤ n)	O(n)	存在大量重复元素