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.
思路：
1.题目要求是O(n)时间复杂度，因此先排序在计算的方法行不通。【排序 sort 的时间复杂度为O(Nlg(N))】.
2.由于数组是无序的，又要求O(n)，首先想到的是用哈希表。
3.用一个哈希表<int,bool>记录每个元素是否使用过，并对每个元素往左右扩展，直到不连续为止，记录最大长度。
class Solution { public: int longestConsecutive(vector<int> &num) { unordered_map<int,char> used; int maxlen=0; for(int i=0;i<num.size();++i) used[num[i]]=false; for(int i=0;i<num.size();++i){ if(used[num[i]]) continue; int thislen=1; for(int j=num[i]+1;used.find(j)!=used.end();++j){ thislen++; used[j]=true; } for(int j=num[i]-1;used.find(j)!=used.end();--j){ thislen++; used[j]=true; } maxlen=max(maxlen,thislen); } return maxlen; } };
