原问题描述如下。
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.
主要是有复杂度要求？否则的话用数组存下来慢慢查找显然也是可以的。对复杂度要求比较高的，所以用哈希表写。
C++里面有库可以直接用，主要是map里面的几个函数要注意一下使用，当时参考的链接是http://blog.csdn.net/flqbestboy/article/details/8184484
需要注意的就是f是一个映射，f.find每次都要判断是不是f.end，还有遍历哈希表的写法是::iterator j; 这样，这个指针j->first是指元素，j->second=f[j->first].
具体代码也贴上来。
1 #include <iostream> 2 #include <map> 3 using namespace std; 4 5 int main(){ 6 int n; 7 int length=-1; 8 int longest=-1; 9 map<int,bool>f;//f是一个从int到bool的映射 10 map<int,bool>::iterator j; 11 cin>>n; 12 for (int i=1;i<=n;i++){ 13 int a; 14 cin>>a; 15 f[a]=true; 16 } 17 for (j=f.begin();j!=f.end();j++){ 18 if (j->second==true){ 19 j->second=false; 20 length=1; 21 int t=j->first+1; 22 while (f.find(t)!=f.end()){ 23 f[t]=true; 24 length++; 25 t++; 26 } 27 t=j->first-1; 28 while (f.find(t)!=f.end()){ 29 f[t]=true; 30 length++; 31 t--; 32 } 33 if (longest<length) longest=length; 34 } 35 } 36 cout<<longest<<endl; 37 return 0; 38 }
leetcode longest consecutive sequence
原文：http://www.cnblogs.com/iamliyou/p/5357050.html
