题目

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) 有待确定。

    public int longestConsecutive(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        Set
   
     set = new HashSet
    
     (); for (int i = 0; i < num.length; i++) { set.add(num[i]); } int max = 0; for (int i = 0; i < num.length; i++) { if (set.contains(num[i])) { int left = num[i] - 1; while(set.contains(left)) { set.remove(left); left--; } int right = num[i] + 1; while(set.contains(right)) { set.remove(right); right++; } if (max < right - left - 1) { max = right - left - 1; } } } return max; }