Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
题解：
因为整数的范围非常大，而且有负数，所以用map来标记和查找元素。
无序找连续元素，可以从某一已有元素开始，递增，递减的查找和它连续的元素是否存在，找过的元素及时从map中删除。
本来想用hash_map，但是没有这个库。。。所以用了map
class Solution {
public:
int longestConsecutive(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<int, int> hmap;
hmap.clear();
int n = num.size();
for(int i=0; i<n; i++){
hmap.insert(pair<int, int>(num[i], i));
}
int ans=0, cnt=0;
map<int, int>::iterator it;
for(int i=0; i<num.size(); i++){
int cur = num[i];
it = hmap.find(num[i]);
cnt++;
if(it!=hmap.end()){
map<int, int>::iterator iter;
while(1){
iter = hmap.find(++cur);
if(iter==hmap.end())
break;
cnt++;
hmap.erase(iter);
}
cur=num[i];
while(1){
iter = hmap.find(--cur);
if(iter==hmap.end())
break;
cnt++;
hmap.erase(iter);
}
if(ans<cnt)
ans = cnt;
cnt=0;
}
cnt=0;
}
return ans;
}
};