1. 问题描述给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。题目看起来还是有点抽象的我们看看官方给的示例。Leetcode官方给出的示例如下现在我们基本上可以理解题目了题目给出一个整数数组里面的元素是乱序的并且可能含有重复的元素我们需要从数组中找出一个连续的序列使得这个序列在所有连续序列中是最长的最后返回这个最长连续序列的长度。2. 解题思路为了达到题目要求的时间复杂度本题我们需要使用到哈希表的空间换时间特性。从上面的示例中可以看出重复的元素对最终获得的结果是没有任何帮助的因此我们要处理掉重复元素。这里我们采用unordered_set它的底层实现是哈希表但和unordered_map不同的是unordered_set只存储key键不存储value值里面的元素是无序的且不允许重复。因此后面当我们将数组nums的元素全部插入到哈希表中时哈希表中最终的元素是不重复的。去掉了重复元素之后我们需要考虑如何对重复元素进行处理。首先我们要明确目标要在哈西表中寻找能组成连续序列的元素对于连续序列一个比较好的办法就是从他的头部或者尾部入手这里我们选择头部。试着思考一下一个连续序列的头部有什么特点显而易见如果一个连续序列的头部为num那么哈希表中是不存在num-1这个元素的。利用好这个特点我们就可以进一步提升程序运行效率。因此我们在遍历哈希表时当遍历到每一个元素num时都检测一下num-1是否存在就能判断元素num是不是序列的头部了。如果num-1不存在说明num确实是一个连续序列的头部我们在依次判断num1num2等等是否存在直到下一个连续的元素不存在为止那么这个序列的长度就显而易见了。我们记录这个序列的长度再和其他序列的长度比较最终得到最长序列的长度。解题思路已经梳理的差不多了下一章我们进入代码实战。3. 具体代码实现完整代码如下classSolution{public:intlongestConsecutive(vectorintnums){unordered_setinthash;//创建哈希表hash.reserve(nums.size());//预分配内存for(intnum:nums){hash.insert(num);//将数组元素插入到哈希表并去掉重复元素}intlongest_count0;//最大序列长度for(constintnum:hash)//这里如果使用引用传递就必须要加const后面解释为什么{if(!hash.count(current_num-1)){intcurrent_count1;//当前正在处理的序列长度intcurrent_numnum;while(hash.count(current_num1)){current_count1;current_num1;}longest_countmax(longest_count,current_count);//更新最大序列长度}}returnlongest_count;}};虽然代码中出现了循环嵌套for里面套while但由于我们加入了只从序列起点开始的判断逻辑每个数字作为序列中间成员时会被直接跳过每个数字只有在作为序列起点被探测或者作为序列成员被计数时才会被访问。因此每个元素在整个过程中最多被访问两次总时间复杂度是线性的O(n)。4. C核心知识点总结在解决最长连续序列这个问题的过程中我们完成的不仅仅是一道算法题还对 C 的几个核心底层机制有了一定的了解。4.1 unordered_set 与 unordered_map深度辨析之前使用的都是unordered_map这道题是我第一次接触到unordered_set。本小节我将详细对比他们两者的差异以更好地了解他们不同的使用场景。unordered_set和unordered_map都是 C STL 中基于哈希表的两个最常用的无序关联容器它们在底层实现上非常相似但在语义和使用场景上有明显区别。下面列表对比二者的特点本题中我们只关心元素是否存在且不需要存储值value因此unordered_set是首选。4.2 预分配内存我们在创建哈希表之后写了这样一行代码hash.reserve(nums.size());为了了解这行代码的作用我们先来看看没有这行代码的情况。如果没有这行代码也就是在常规情况下我们向哈希表插入元素随着元素的增多当达到负载因子的阈值时就会触发rehash导致重新哈希这就涉及到申请新内存、重新计算所有元素的哈希值并搬迁。这会大幅拖慢程序的运行效率。在这种情况下预分配的作用就体现出来了。我们使用reserve提前告知容器的预期规模能够有效地避免程序运行过程中动态扩容的开销提升程序的运行效率。由于数组nums中的元素可能存在重复我们为哈希表预分配的内存一定是大于或者等于哈希表实际占用内存的因此直接使用nums.size()即可。4.3 key的只读属性在上面代码的实现中有这样一行代码for(constintnum:hash)我在注释中提到如果这里使用了引用传递那么就必须要加上const。下面解释一下为什么。哈希表中的key决定了它存储在哪个桶里如果允许通过引用随意修改key的值那么该key将由于哈希值改变而导致在表中丢失。此外C 标准库规定unordered_set的迭代器指向的是const元素。因此若使用引用传递必须加上const限定符否则编译器会为了保护数据结构完整性而拒绝编译。这里可能有人会问如果不使用引用传递直接使用常规的值传递可以吗答案是理论和实际上都是完全行得通的但是程序的运行效率会被大大拖慢。因为值传递会将原本的值再拷贝一份然后使用。而如果使用引用传递num就只是原本数据的一个别名不会有额外的拷贝开销从而能够提升程序的运行效率前提是加上const。4.4 count和findunordered_set和unordered_map中的count()与find()是最常用的两种判断 key 是否存在的方法。他们的区别如下count当要判断的key存在时返回 1不存在时返回 0。find当要判断的key存在时返回指向该元素的迭代器不存在时返回end()。这样看来它们的使用场景基本就划分开了。当我们只需要知道某个key是否存在而不需要value时就可以使用count。当我们需要拿到value或者修改value时就必须使用find。4.5 std::max详解std::max是定义在 C 标准库头文件algorithm中的一个函数模板它的基本功能是比较两个或多个值并返回其中的最大值。我们常规的选出最大值的写法如下if(current_countlongest_count){longest_countcurrent_count;}但是使用std::max会更加简洁longest_countstd::max(longest_count,current_count);使用std:max有个需要注意的点max的参数类型必须完全相同如果不同必须强制类型转换。从 C11 开始就可以通过初始化列表大括号一次性比较多个数intresultmax({a,b,c,d});此外std::max内部通常是通过常引用传递参数的。这意味着即使你比较的是两个巨大的对象比如两个超长的字符串它也不会产生额外的内存拷贝性能非常出色。4.6 insert和push_back辨析可能有人会存在这样的疑惑为什么在vector中我们习惯用push_back而到了unordered_set却必须用insert其实这背后的逻辑完全不同。push_back从字面意思来看就是从后面推入实际上的原理也大致相同。适用的容器有vector、list、deque等序列式容器。它有一个前提——容器必须是有序的也就是说新来的元素必须放在队伍的最末尾。insert从字面意思来看是插入适用unordered_set、set、map等关联式容器。关联式容器尤其是哈希表并不关心先后顺序。就拿哈希表来说一个元素具体放在哪个桶是要根据计算出来的哈希值决定的而不是简单的按顺序放。如果你尝试对哈希表使用push_back编译器会直接报错。原因很简单哈希表并没有末尾的概念。到这里代码中涉及到的 C 知识点已经梳理完了希望对大家有所帮助。本文结束。