【哈希】LC 128.最长连续序列

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接128.最长连续序列2、题目描述二、个人思路整理1、思路分析思路参考最长连续序列、两个关键优化O(n) 时间复杂度Python/Java/C/C/Go/JS/Rust、https://leetcode.cn/problems/longest-consecutive-sequence/solutions/276931/zui-chang-lian-xu-xu-lie-by-leetcode-solution/comments/2283513/此题复杂度限制在O(n)因此不能使用排序快排复杂度为O(nlogn)超出题目复杂度要求所以需要换一种思路核心就是快速判断数组中的每个元素是否可能是某一个连续序列的起点开头元素快速判断想到利用哈希表如果可能是则进行遍历查找后续递增元素是否存在若一定不是则直接跳过后续步骤进行数组中下一个元素的判断。如何进行判断数组中的元素是否可能是最长连续序列的开头元素呢先说不可能的情况当遍历到的元素值为i但数组中存在i-1那么说明当前元素就没有必要进行后续递增序列的计算因为以i-1开头的序列一定要比以i开头的序列要长不论这个以i-1开头的连续序列长度是先与以i开头的连续序列长度计算的还是迟于它最终当前以i开头计算出的连续序列的最大长度都会被更新所以这种情况没有必要再对以i开头的连续序列长度的计算排除上述不可能情况其他情况都有可能咱们需要依次计算以其他元素开头的连续序列的长度然后最终得到最大的长度。由于原数组可能存在重复元素所以我们需要去重后再进行计算以减低算法复杂度。2、解题代码classSolution{public:intlongestConsecutive(vectorintnums){unordered_setints;intmax_len0;//记录全局最大长度for(autonum:nums){s.insert(num);}for(autoi:s){if(s.count(i-1))continue;//如果i-1存在说明i不是起点跳过计算//如果找到一个起点计算以这个起点开始的序列长度inttmpi1;intcur_len1;//依次在哈希表中查找递增的元素是否存在存在则当前序列长度加一同时继续判断下一个递增元素while(s.count(tmp)){cur_len;tmp;}max_lenmax(max_len,cur_len);}returnmax_len;}};三、知识风暴空间换时间利用哈希表O(1)的查询效率代替暴力循环去匹配的过程