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.

Solution: Because it requires O(n) complexity, we can not solve the problem by sorting the array first. Sorting takes at least O(nlogn) time.

We can use a HashSet to add and remove elements. HashSet is implemented by using a hash table. Elements are not ordered. The add, remove and contains methods have constant time complexity O(1).

遇到不能排序又要复杂度O(n)有序的问题，只能增加空间复杂度，用hashset或者hashtable 

public class Solution {
    public int longestConsecutive(int[] num) {
        if(num == null || num.length == 0)
            return 0;
        
        HashSet set = new HashSet();
        int max = 1;

        for(int i = 0; i < num.length; i++) {
            set.add(num[i]);
        }
        
        for(int i = 0; i < num.length; i++) {
            int left = num[i] - 1;
            int right = num[i] + 1;
            int count = 1;
            
            while(set.contains(left)) {  //找比num[i]小1的值
                count++;
                set.remove(left);
                left--;
            }
            while(set.contains(right)) {  //找比num[i]大1的值
                count++;
                set.remove(right);
                right++;
            }
            max = Math.max(max, count);
        }
        
        return max;
    }
}