Description:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Link:
https://leetcode.com/problems/longest-consecutive-sequence/description/
解題方法：
這道題要求在O(n)時(shí)間解出，所以不能對(duì)數(shù)組進(jìn)行排序棺滞。
解題思路參考：https://blog.csdn.net/fightforyourdream/article/details/15024861
O(n)解法為：把所有數(shù)都存到hashset中去苟径，每遇到一個(gè)數(shù)，就把比它大的和比它小的連續(xù)的數(shù)都找一遍，在找的過程中把這些數(shù)都從hashset中刪掉嚼吞，防止重復(fù)查找盒件。
比如例子：100, 4, 200, 1, 3, 2都加入hashset
當(dāng)找100時(shí)，把100刪掉舱禽，此時(shí)hashset: 4, 200, 1, 3, 2
.
.
.
當(dāng)找到4時(shí)炒刁，找完以后的hashset: 200 （100在第一輪被刪掉，1 2 3都在找比4小的連續(xù)數(shù)過程中都被刪掉）
Time Complexity：
O(N)
完整代碼：
int longestConsecutive(vector<int>& nums) {
unordered_set<int> hash;
for(int i: nums)
hash.insert(i);
int result = 0;
for(int i: nums) {
int cnt = 1;
hash.erase(i);
int temp = i - 1;
//find less
while(hash.find(temp) != hash.end()) {
cnt++;
hash.erase(temp--);
}
temp = i + 1;
while(hash.find(temp) != hash.end()) {
cnt++;
hash.erase(temp++);
}
result = max(result, cnt);
}
return result;
}
