大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天逛脉脉看到有人透露今年鹅厂的校招本周就要开奖了，据说研发小白菜价已经27k起步了，很多老员工看到后纷纷表示倒挂的越来越严重了，不少老鹅表示自己工作三年多的时候都没有现在的校招生薪资高。也有人认为薪资不高一点人才就被其他厂抢光了。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「最长连续序列」。
题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
举个例子：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路解析
本题的思路比较类似于广度优先搜索。
把数组
nums的所有元素存到hashset中。遍历数组
nums，明确连续序列的起点，对于数组nums中的元素num，如果num - 1不在hashset中，就把num作为一个连续序列的起点，进入步骤3。从连续序列的起点
num开始，不断去hashset中寻找num + i，i >= 1。直到num + len不在hashset中(以num为起点的序列此后就不再连续)，更新最长连续序列的长度max_len = max(max_len, len)。如果数组nums已遍历完，进入步骤4，否则进入步骤2。返回
max_len。
下面我们给出c++和python两种代码实现。
C++代码
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int max_len = 0;
unordered_set<long long> nums_set;
int nums_len = nums.size();
//把所有的元素保存在set中
for (int i = 0; i < nums_len; ++i) {
nums_set.emplace(nums[i]);
}
for (auto& num:nums) {
//num-1不在set中 保证num是连续序列的起始元素
if (nums_set.find(num - 1) == nums_set.end()) {
int len = 0;
//num+len在set中 说明num～num+len是连续的
while (nums_set.find(num + len) != nums_set.end()) {
++len;
max_len = max(len, max_len);
}
}
}
return max_len;
}
};
python代码
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
max_len = 0
nums_set = set(nums)
nums_len = len(nums)
# 把所有的元素保存在set中
for num in nums:
# num-1不在set中 保证num是连续序列的起始元素
if num - 1 not in nums_set:
length = 0
# num+len在set中 说明num～num+len是连续的
while num + length in nums_set:
length += 1
max_len = max(length, max_len)
return max_len
复杂度分析
时间复杂度： O(n)，只需要遍历一遍数组，其中n为数组的大小。
空间复杂度： O(n)，需要借助一个hashset，其中n为数组的大小。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
