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.

这个题目第一感觉就是排序完了再进行遍历一次数组就能完成功能，但是我们发现其实把整体所有元素进行排序似乎是很浪费的事情。考虑到时间复杂度为O(n) ，看到一个非常精彩的思路，建立一个Map，Map中存放两个整型值代表两个值之间都是连续的。这样只需要遍历一次数组元素就能实现功能，非常精彩算法思想。 

public class Solution {	 public int longestConsecutive(int[] num) {		 // 明白 HashMap 存放值含义： 表明 第一个整型值到第二个整型值是连续的区间         Map<Integer, Integer> seq = new HashMap<Integer, Integer>();         int longest = 0;         for (int i = 0; i < num.length; i++) {             if (seq.containsKey(num[i]))             	 continue;             int low= num[i],upp=num[i];             if (seq.containsKey(num[i] - 1)) // 如果有，获得num[i]-1向下连续数字连续区间的下界。                 low = seq.get(num[i] - 1);             if (seq.containsKey(num[i] + 1)) // 如果有，获得num[i]+1向上连续数字连续区间的上界。                 upp = seq.get(num[i] + 1);             // 更新longest             longest = Math.max(longest, (upp - low)+ 1);             seq.put(num[i],num[i]);             // 更新连续区间 。必须存放两个一个由小到大和由大到小两个区间。才能在上面寻找上界和下界             seq.put(low, upp);                            seq.put(upp, low);                       }         return longest;     }}

Longest Consecutive Sequence