大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位复旦毕业的同学在华为od工作了两年，工作不太顺心，想考研重开，打算研究生毕业后找个国企的工作。
评论区大部分人都不建议他考研，认为读三年研究生行情可能会更差，说不定毕业还是要进od。还有一些脉友认为研究生毕业还是做研发有点重蹈覆辙的意思，有复旦的背景，还不如直接进外企。读研一般要两到三年，这段时间完全是没有收入的，而且确实无法保证学历提升后一定有更好的工作机会，读了三年研拿不到本科时offer的例子比比皆是，不如换个工作看看现状能否有所改善，实在不行再走考研这条路。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道华为OD的面试原题「最长连续序列」。
题目描述
给定一个未排序的整数数组 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 ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
