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(nlogn) > O(n)，故不能排序。 所以想到用hashmap 或者双指针做。这题显然用双指针无法做。

由于题目没有说array无重复，所以首先去重， 使用hashmap。

然后想到了以某个节点为中心向两边发散，将能够由它组成的连续数的最大长度找出来。 由于要保持O(n)，所以每个节点最多访问一边。 所以采用边发散边删的方法，这样在遍历时就不会重复访问了。

最后找出最大长度即可。

1 public class Solution { 2     public int longestConsecutive(int[] num) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         HashMap
     
       hm = new HashMap
      
       (); 6         for(int i = 0; i < num.length; i ++){ 7             if(!hm.containsKey(num[i])){ 8                 hm.put(num[i],1); 9             }10         }11         int max = 0;12         for(int i = 0; i < num.length; i ++){13             if(hm.containsKey(num[i])){14                 int cur = 1;15                 int j = 1;16                 hm.remove(num[i]);17                 while(hm.containsKey(num[i] + j)){18                     cur ++;19                     hm.remove(num[i] + j);20                     j ++;21                 }22                 j = 1;23                 while(hm.containsKey(num[i] - j)){24                     cur ++;25                     hm.remove(num[i] - j);26                     j ++;27                 }28                 if(cur > max){29                     max = cur;30                 }31             }32         }33         return max;34     }35 }
      
     

 第4遍：

1 public class Solution { 2     public int longestConsecutive(int[] num) { 3         if(num == null || num.length == 0) return 0; 4         HashSet
     
       numSet = new HashSet
      
       (); 5         for(int i = 0; i < num.length; i ++){ 6             if(!numSet.contains(num[i])) numSet.add(num[i]); 7         } 8         int result = 0; 9         int curMax = 0;10         for(int i = 0; i < num.length; i ++){11             if(numSet.contains(num[i])){12                 curMax = 1;13                 numSet.remove(num[i]);14                 int j = num[i] - 1;15                 int k = num[i] + 1;16                 while(numSet.contains(j)){17                     curMax ++;18                     numSet.remove(j);19                     j --;20                 }21                 while(numSet.contains(k)){22                     curMax ++;23                     numSet.remove(k);24                     k ++;25                 }26                 result = Math.max(result, curMax);27             }28         }29         return result;30     }31 }