题目描述
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example1:
Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
解题思路
- 使用一个unorder_set
- 遍历这个序列，如果这个序列的元素存在，前后继续遍历
- 直到不存在为止
- 这里如果这样写会超时
- 想一想，如果遍历4元素，那么1，2，3，4 肯定会检查一遍
- 如果遍历1元素 1，2，3，4仍会检查一遍
- 当我们这个集合有这个值的时候，要把这个值给去掉，免得重复
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.size() == 0){
return 0;
}
unordered_set<int> sets(nums.begin(), nums.end());
int pre = 0;
int next = 0;
int res = 1;
for(auto& i : nums){
if(sets.count(i) != 0){
sets.erase(i);
}else{
continue;
}
pre = i - 1;
next = i + 1;
while(sets.count(pre) != 0){
sets.erase(pre);
pre -= 1;
}
while(sets.count(next) != 0){
sets.erase(next);
next++;
}
res = max(res, next - pre - 1); // 0, 5 是不存在的，只存在 1，2，3，4 -》 这4个元素
}
return res;
}
};
