Description

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

HashSet, time O(n), space O(n)

将nums存在HashSet中，然后遍历nums，对于每个元素都尽量向两边扩展，同时移除set中元素，就行了。

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null) {
            return -1;
        }
        
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }
        
        int maxLen = 0;
        for (int n : nums) {
            if (!set.contains(n)) {     // already used
                continue;
            }
            
            int len = 1;
            set.remove(n);
            // extend left
            for (int i = n - 1; set.contains(i); --i) {
                ++len;
                set.remove(i);
            }
            // extend right
            for (int i = n + 1; set.contains(i); ++i) {
                ++len;
                set.remove(i);
            }
            
            maxLen = Math.max(maxLen, len);
        }
        
        return maxLen;
    }
}