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.
思路：
这题首先想到的是，利用数组将num中的每个数字当做index放入一个新的数组中，然后寻找连续的填充过的范围即可。
但是，题目中并没有告诉你数字的范围，如果类似于 [1,100000,-10000]这样的num，那么就没法做了。首先，数字范围相差巨大
即便申请了足够的空间，也会造成空间上的巨大浪费。其次，负数是有可能存在的。因此，下标是无法出现负数的情况下，该方案被废弃。
再想，如果用HashMap来存储，num中的每一个值均为key，value代表是否访问过这个num的值，而从该key向上，向下分别查找一下相应的key
看是否存在对应的key就能知道目前这个num的值所在的连续数列的长度了。而每次访问完一个key，就修改它的值为true，意味着已经访问过。
而对于已经访问过的key，则一定有他所在的连续数列中的所有数字都访问过。因此，可以做到每个key（num中的值）都能仅访问一遍。
做到了O（n）。
AC代码：
public class Longest_Consecutive_Sequence {
public int longestConsecutive(int[] num) {
HashMap<Integer,Boolean> map = new HashMap<Integer, Boolean>(num.length);
for(int i=0;i<num.length;i++){
map.put(num[i],false);
}
int max = 0;
for(int i=0;i<num.length;i++){
int len = 0;
if(!map.get(num[i])){
len++;
map.put(num[i],true);
int j = num[i]-1;
while(map.containsKey(j) && !map.get(j)){
len++;
map.put(j,true);
j--;
}
j = num[i]+1;
while(map.containsKey(j) && !map.get(j)){
len++;
map.put(j,true);
j++;
}
max = max>len?max:len;
}
}
return max;
}
public static void main(String[] args){
Longest_Consecutive_Sequence longest_consecutive_sequence = new Longest_Consecutive_Sequence();
int[] num = {100,4,200,1,3,2};
System.out.println(longest_consecutive_sequence.longestConsecutive(num));
}
}