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.

Discuss

题目要求O(N)的时间复杂度，显然不能排序，考虑哈希，从某个数开始递增递减查询，更新最长长度，这里需要考虑一些退化的情况：

当输入是形如【1,2,3,4,5.......n】的已经排好序的连续输入时候，算法可能退化成O（n^2），故考虑在哈希查询到的时候一并删除该元素，并在后面加判断长度是否已经

大于等于数组长度，java code :

public class Solution {  
    public int longestConsecutive(int[] num) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(num.length == 0)  
            return 0;  
        if(num.length == 1)  
            return 1;  
        HashSet<Integer> hash = new HashSet<Integer>();  
        for(int i = 0; i < num.length; i++)  
        {  
            hash.add(num[i]);  
        }  
        int res = 0;  
        for(int i = 0; i < num.length; i++)  
        {  
            int tmplen = 1, tmpnum;  
            tmpnum = num[i] + 1;  
            while(hash.contains(tmpnum))  
            {  
                hash.remove(tmpnum);  
                tmplen++;  
                tmpnum++;  
            }  
            tmpnum = num[i] - 1;  
            while(hash.contains(tmpnum))  
            {  
                hash.remove(tmpnum);  
                tmplen++;  
                tmpnum--;  
            }  
            if(tmplen > res)  
                res = tmplen;  
            if(res >= num.length)  
                break;  
        }  
        return res;  
    }  
}

补充：软件开发 , Java ,