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.

Analysis

• 使用 HashSet 建哈希表
• 遍历数组
• 依次往左往右搜相邻数，搜到了就从 Set 中删除
• 末尾更新最大值

Code

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums==null || nums.length==0) return 0;
        if (nums.length==1) return 1;

        Set<Integer> set = new HashSet<Integer>();

        for (int n:nums) {set.add(n);}

        int res = 0;

        for (int n:nums){
            int cs = 0;
            int small = n;
            int large = n;
            while (set.contains(--small)){ cs++; set.remove(small);}
            while (set.contains(++large)){ cs++; set.remove(large);}
            set.remove(n);
            res = Math.max(res, cs+1);
        }

        return res;
    }
}

Reference

Yuanbin