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

前言

本专栏文章为《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/

1. 此题复杂度限制在O(n)，因此不能使用排序（快排复杂度为O(nlogn)超出题目复杂度要求）；
2. 所以需要换一种思路，核心就是快速判断数组中的每个元素是否可能是某一个连续序列的起点（开头）元素（快速判断想到利用哈希表），如果可能是则进行遍历，查找后续递增元素是否存在；若一定不是，则直接跳过后续步骤，进行数组中下一个元素的判断。
3. 如何进行判断数组中的元素是否可能是最长连续序列的开头元素呢？

• 先说不可能的情况：当遍历到的元素值为i但数组中存在i-1，那么说明当前元素就没有必要进行后续递增序列的计算（因为以i-1开头的序列一定要比以i开头的序列要长，不论这个以i-1开头的连续序列长度是先与以i开头的连续序列长度计算的还是迟于它，最终当前以i开头计算出的连续序列的最大长度都会被更新，所以这种情况没有必要再对以i开头的连续序列长度的计算）；
• 排除上述不可能情况，其他情况都有可能，咱们需要依次计算以其他元素开头的连续序列的长度，然后最终得到最大的长度。

4. 由于原数组可能存在重复元素，所以我们需要去重后再进行计算，以减低算法复杂度。

2、解题代码

classSolution{public:intlongestConsecutive(vector<int>&nums){unordered_set<int>s;intmax_len=0;//记录全局最大长度for(autonum:nums){s.insert(num);}for(autoi:s){if(s.count(i-1))continue;//如果i-1存在，说明i不是起点，跳过计算//如果找到一个起点，计算以这个起点开始的序列长度inttmp=i+1;intcur_len=1;//依次在哈希表中查找递增的元素是否存在，存在则当前序列长度加一同时继续判断下一个递增元素while(s.count(tmp)){cur_len++;tmp++;}max_len=max(max_len,cur_len);}returnmax_len;}};

三、知识风暴

• 空间换时间：利用哈希表O(1)的查询效率，代替暴力循环去匹配的过程