0128.最长连续序列看到这个题目的第一眼想到的自然是排序算法直接排序遍历但是复杂度达到了o(nlogn)不符合题目所要求的o(n)。对于n复杂度的算法我第一个想到的是使用哈希map直接遍历一遍数组对于每个数字查找当前数字的「前驱连续长度」即num-1 所在序列的长度和后继长度。如果当前数字未被计算过这是由于可能出现重复数字那么就可以合并前后续列长度并且更新左右边界长度。看到这里大家可能会有疑问为什么只需要更新左右边界长度呢这是由于每次遇到新的数字时只有边界的数字会参与计算中间数字对应哈希值不会被使用到所以无需更新且一定小于边界值不会影响答案。classSolution{public:intlongestConsecutive(vectorintnums){intans0;unordered_mapint,intmap;for(intnum:nums){// 1. 查找当前数字的「前驱连续长度」num-1 所在序列的长度intprevmap.find(num-1)map.end()?0:map[num-1];// 2. 查找当前数字的「后继连续长度」num1 所在序列的长度intsufmap.find(num1)map.end()?0:map[num1];// 3. 仅当数字未被处理过时避免重复计算if(map.find(num)map.end()){// 4. 合并前后序列当前数字的序列长度 前驱 后继 自身1map[num]prevsuf1;// 5. 更新序列「左边界」的长度关键map[num-prev]map[num];// 6. 更新序列「右边界」的长度关键map[numsuf]map[num];ansmax(ans,map[num]);}}returnans;}};接下来如果要理解如何从第一个哈希表记录长度的算法转化为题解的哈希集合找连续序列起点的算法核心是换一种思路解决「最长连续序列」问题—— 从「合并序列」转向「找序列起点并统计长度」。第一个算法的核心是「动态合并」遍历每个数字时合并其前后的连续序列并用哈希表记录序列长度仅更新边界。但这个思路有两个「不直观」的点需要处理「重复数字」map.find(num) map.end()要维护「序列边界的长度」逻辑上需要理解「为什么只更新边界」我们可以思考有没有更直接的方式——既然是「连续序列」那每个序列都有唯一的「起点」即没有前驱数x-1的数只要找到所有起点再逐个统计以该起点开头的连续序列长度即可。这就是第二个算法的核心思路大部分是这种思路就不过多赘述了。