LeetCode热题100精讲——Top3:最长连续序列【哈希】

你好，我是安然无虞。

题目背景

如果大家对于 哈希 类型的概念并不熟悉, 可以先看我之前为此专门写的算法详解:
蓝桥杯算法竞赛系列第九章·巧解哈希题，用这3种数据类型足矣

最长连续序列

题目链接：最长连续序列

解题思路：

这道题最直接的想法就是排序，排序之后连续的序列就很容易找到了。但是排序的时间复杂度是 O(NlogN)，而题目要求我们时间复杂度为 O(N)，所以我们需要另想办法。

想找连续序列，首先要找到这个连续序列的开头元素，然后递增，看看之后有多少个元素还在 nums 中，即可得到最长连续序列的长度了。

由此我们可以想到用空间换时间的思路，把数组元素放到哈希集合里面，然后去寻找连续序列的第一个元素，即可在 O(N) 时间找到答案。

比方说 nums = [8,4,9,1,3,2]，我们先找到 1，然后递增，找到了 2, 3, 4，这就是一个长度为 4 的序列。

代码详情：

C++解法

class Solution {
public:int longestConsecutive(vector<int>& nums) {// 本题重点在于找到连续序列的第一个值// 转化成哈希集合，方便快速判断是否存在某个元素unordered_set<int> set;for (int num : nums) {set.insert(num);}// 记录结果int res = 0;for (int num : set) {if (set.count(num - 1)) {// num 不是连续子序列的第一个，跳过continue;}// num 是连续子序列的第一个，开始继续计算连续子序列的长度int curNum = num;int curLen = 1;while (set.count(curNum + 1)) {curNum += 1;curLen += 1;}// 更新最长连续序列的长度res = max(res, curLen);}return res;}
};

Python解法

集合的优势就是能够快速判断是否存在某个元素.

class Solution:def longestConsecutive(self, nums: List[int]) -> int:# 本题重点在于找到连续序列的第一个值set_nums = set(nums) # 将数组存放到哈希集合中res = 0 # 记录结果for num in set_nums:# 判断当前值是不是连续序列的第一个值if num - 1 in set_nums:continuecurNum = numcurLen = 1while curNum + 1 in set_nums:curNum += 1curLen += 1res = max(res, curLen)return res

遇见安然遇见你，不负代码不负卿。

谢谢老铁的时间，咱们下篇再见～