题目描述#
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入： nums = [100,4,200,1,3,2]
输出： 4
解释： 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入： nums = [0,3,7,2,5,8,4,6,0,1]
输出： 9
示例 3：
输入： nums = [1,0,1,2]
输出： 3
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
解题思路#
朴素解->哈希表#
首先来看最朴素的思想，当我们拿到一个数 x 时，以他作为连续序列的头元素，紧接着去寻找列表中有没有 x+1，直到找不到下一个 x+1，更新最长连续长度
这样的时间复杂度是 的，显然不符合题目要求，我们尝试减小时间复杂度。
我们知道，在哈希表中查询数据的时间复杂度是 的，因此，我们可以先将列表中的数据都存进哈希表中，这样找 x+1 的时间复杂度就从 变成了 ，总时间复杂度降到了
当我们拿到一个数 x 时，首先判断列表中有无 x-1，假如有，那么以 x 打头的列表必然不可能是最长序列，可以直接略过。假如没有，那么就依次寻找 x+1，更新序列长度。
至于 c++中如何使用哈希表，请见哈希值与哈希表
最后可以很顺利地写出代码：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int,bool> HashTable;
for(int i=0;i<nums.size();i++) {
HashTable[nums[i]] = true;
}
int max_length=1;
for(int i=0;i<nums.size();i++) {
int length=1,num=nums[i];
if(HashTable[num-1]) continue;
while(HashTable[num+1]) {
length++;
num++;
}
max_length = max(max_length,length);
}
return max_length;
}
};结果发现通过不了，分析原因：
- 边界情况，当数组为空时应特判
- 考虑去重，当数据中存在很多重复数时，会极大增加时间复杂度
对于去重，我们采用 unordered_set，这样一举两得，在去重的同时能够以 的时间复杂度查询键值
具体用法请见哈希值与哈希表
改进后代码：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.size()==0) return 0;
unordered_set<int> num_set;
for(const int& num : nums) {
num_set.insert(num);
}
int max_length=1;
for(const int& num : num_set) {
int length=1,cur_num=num;
if(num_set.count(cur_num-1)) continue;
while(num_set.count(cur_num+1)) {
length++;
cur_num++;
}
max_length = max(max_length,length);
}
return max_length;
}
};