[LeetCode] Longest Consecutive Sequence

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. 先sort array，时间复杂度为logn， 然后再遍历数组找出连续的sequence。
2. 先scan一遍数组，然后放到hashmap里，然后再以每个数为中心，向两边找到最大的连续sequence. 每次扫完一个element后，将其标为false, 以避免以后重复扫描。

Java code

 public int longestConsecutive(int[] num) {
        Arrays.sort(num);
        int max = 0;
        int len = 1;
        
        for(int i = 0; i < num.length - 1; i++){
            if(num[i] == num[i+1] - 1){
                len++;
            }else if(num[i] < num[i+1] - 1){
                max = len > max? len : max;
                len = 1;
            }
        }
        
        max = max > len ? max : len;
        return max;
    } 

 public int longestConsecutive2(int[] num) {
       HashMap tmp = new HashMap();
       int maxLen = 0;
       
       for(int i = 0; i < num.length; i++){
           tmp.put(num[i], true);
       }
       
       for(int i = 0; i < num.length; i++){
           int len = 0;
           int num0 = num[i];
           
           while(tmp.containsKey(num0) && tmp.get(num0)){
               len++;
               tmp.put(num0, false);
               num0++;
           }
           
           num0 = num[i]-1;
     
            while(tmp.containsKey(num0) && tmp.get(num0)){
               len++;
               tmp.put(num0, false);
               num0--;
           }
           
           maxLen = Math.max(len, maxLen);
       }
       
       return maxLen;
    }