题目描述
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例：
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
题目链接： https://leetcode-cn.com/problems/longest-consecutive-sequence/
思路1
使用哈希表来做，并且使用 c++ 的 map 来构造哈希表。map 默认是按照 key 升序排序的。我们先将数组中的数字插入到 map 中，然后从头遍历 map，这样遍历得到的 key 序列就是一个有序序列。这样问题就转化成了在有序序列中找最长连续序列的长度。可以用动态规划来做：
- 令当前最长连续序列的长度 ans = 1，设置计数器 cnt = 1，表示当前连续序列的长度；
- 遍历哈希表：
- 如果当前元素的 key 和前一个元素的 key 相等，说明连续，cnt++;
- 否则说明不连续，遇到了新的连续序列，则 ans = max(ans, cnt)，cnt = 1；
- 返回 max(ans, cnt)；
代码如下：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty()) return 0;
map<int, int> hash;
for(int i=0; i<nums.size(); i++) hash[nums[i]]++;
vector<int> dp(hash.size(), 0);
auto it = hash.begin();
int ans = 1;
int cnt = 1;
auto pre = hash.begin(); // 当前元素的前一个元素
for(; it!=hash.end(); it++){
if(it!=hash.begin()){
if(it->first - pre->first == 1){
cnt++;
}else{
ans = max(cnt, ans);
cnt = 1;
}
}
pre = it;
}
return max(ans, cnt);
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
思路2
遍历数组 nums，当遍历当前元素 nums[i] 时，判断 nums[i]-1 是否在数组中，如果不在的话，循环判断 nums[i]+cnt 是否在数组中，如果 nums[i]~nums[i]+cnt 都在数组中，那么我们就找到了一个长度为 cnt 的连续序列。记录最长的 cnt 作为答案。可以用 set 来判断一个元素是否在数组中出现。
代码如下：
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty()) return 0;
unordered_set<int> s;
for(int num:nums) s.insert(num);
int ans = 1;
for(int i=0; i<nums.size(); i++){
if(s.count(nums[i]-1)==0){ // nums[i]-1 没有在数组中出现，这一步判断很重要
int cnt = 1;
int curNum = nums[i];
while(s.count(curNum+1)){
curNum++;
cnt++;
}
ans = max(ans, cnt);
}
}
return ans;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
参考
后记
这是我刷的 LeetCode 的第 150 题，这段时间刷题速度明显下降了，接下来要加油。