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.
题解：首先构建一个hashmap，键值为num中的所有元素，这样查找一个元素是否在num中就只需要O(1)的时间了。
接下来以上面给定的例子来说明算法：
比如上述num数组中第一个元素是100，那么就找101或者99在不在num中，发现不在；
num中第二个元素是4，那么就找3或者5是否在num中，发现3在num中，而5不在；于是继续找2在不在num中，然后找1在不在num中.....最终知道有4，3，2，1这么一个长度为4的序列。在这个遍历过程中，因为已经找到了序列4，3，2，1，所以如果以后遍历到3的时候再找到的序列3，2，1已经没有意义了（肯定比当前的最长序列短），所以3，2，1这三个元素在未来的遍历中，我们都不需要考虑了，这里就把它们在hashmap中对应的值改成1，作为标志。
num中第三个元素是200，那么就找199或者201是否在num中，发现都不在；
num中还有元素1，3，2，基于上述描述的原因，就不再遍历了。
这样就保证了每个元素最多遍历一次，时间复杂度为O(n)。
示例图如下;
代码如下：
public class Solution {
public int longestConsecutive(int[] num) {
int answer = 0;
HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
for(int i:num)
map.put(i, 0);
for(int i:num){
if(map.get(i) == 1)
continue;
int currMax = 1;
int tmp = i-1;
//left
while(map.containsKey(tmp)){
map.put(tmp, 1); //we have visited tmp,so we don't start with tmp in the future
currMax++;
tmp--;
}
tmp = i+1;
while(map.containsKey(tmp)){
map.put(tmp, 1);
currMax++;
tmp++;
}
if(currMax > answer)
answer = currMax;
}
return answer;
}
}