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)时间解出，所以不能对数组进行排序。
解题思路参考：https://blog.csdn.net/fightforyourdream/article/details/15024861
O(n)解法为：把所有数都存到hashset中去，每遇到一个数，就把比它大的和比它小的连续的数都找一遍，在找的过程中把这些数都从hashset中删掉，防止重复查找。
比如例子：100, 4, 200, 1, 3, 2都加入hashset
当找100时，把100删掉，此时hashset: 4, 200, 1, 3, 2
.
.
.
当找到4时，找完以后的hashset: 200 （100在第一轮被删掉，1 2 3都在找比4小的连续数过程中都被删掉）
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;
}
