Leetcode 最长连续序列

在这里插入图片描述

算法流程：

哈希集合去重：
- 通过将数组中的所有元素放入 unordered_set，自动去除重复元素。集合的查找操作是 O(1)，这为后续的快速查找提供了保证。
遍历数组：
- 遍历数组中的每一个元素。对于每个元素，首先检查它是否是某个连续序列的第一个元素。
- 具体地，如果当前元素的前一个元素 (num - 1) 不在集合中，说明当前元素有可能是某个序列的开始。这是关键步骤，因为如果 num - 1 在集合中，说明当前元素是某个序列的中间元素，不需要再处理。
序列长度统计：
- 当确定当前元素为某个序列的起点时，进入一个循环，检查当前元素的后一个元素 (num + 1、num + 2、… ) 是否存在于集合中。
- 利用 count() 来检查每个右邻元素是否存在，如果存在则将 currentStreak 加 1 继续统计，直到右邻元素不再存在。
更新最大长度：
- 每当一个序列结束时，使用 max() 函数更新全局的最大序列长度 longestStreak。

代码结构与逻辑重点：

哈希集合的使用 保证了我们能够在 O(1) 时间内查找某个元素是否存在。
通过判断左邻元素是否存在 确保我们只对可能的序列起点进行处理，避免了对所有元素都重复计算。
count() 函数的 O(1) 查找时间 确保了我们能在常数时间内判断右邻元素是否存在，从而以线性时间完成整个数组的遍历和处理。

通过哈希集合的使用，算法避免了排序操作（O(n log n)），从而保证了线性时间复杂度 O(n)。

算法思路：

首先利用数组所有元素来初始化一个哈希集(unordered_set)，由于集合性质，这一步会自动去除重复元素。

然后我们再去遍历数组每个元素，仅当当前元素是可能是某个最长连续序列的第一个元素时 (左邻元素不存在于哈希集中)，我们进行序列长度统计。

所以，如果当前元素的前一个相邻元素(num - 1)存在于哈希集中，那么说明当前元素必然不可能是某个最长连续序列的开始元素。这种情况下我们跳过不予处理。

再回到如果当前元素的确是某个可能的最长连续序列的第一个元素时，我们利用 STL 容器的成员函数 count() 来判断当前元素的右邻元素是否存在于哈希集中，并使用一个新的变量(currentStreak)来统计当前最长连续序列的长度,

在 unordered_set 中，count() 函数的主要作用是检查某个值是否存在于集合中。因为 unordered_set 只存储唯一的元素，因此 count() 要么返回 0，要么返回 1：

返回 0：表示该元素不在集合中。
返回 1：表示该元素在集合中。

如果右邻元素存在于哈希集，那么currentStreak 加1，如果不存在于哈希集中则直接跳出循环。

每当跳出循环时，意味着最近一次处理的连续序列的长度已经统计结束，需要和上一次处理的连续序列的长度(currentStreak)进行 max 对比并更新currentStreak

class Solution {
public:int longestConsecutive(vector<int>& nums) {//初始化一个无序集合并且将nums数组中的元素全部加入到这个集合中unordered_set<int> numSet(nums.begin(), nums.end());//最长序列长度int longestStreak = 0;for(int num : nums) {if(numSet.count(num - 1) == 0) {//如果当前元素的前一个连续元素并不存在于集合中，说明当前元素有可能是一个最长连续序列的开头//并且这个最长连续序列目前至少长度为1int currentStreak = 1;//然后逐个+1并在集合中判断是否存在，直到不存在时终止int currentNum = num;while(numSet.count(currentNum + 1)) {currentStreak++;currentNum++;}longestStreak = max(longestStreak, currentStreak);}}return longestStreak;}
};