128. Longest Consecutive Sequenc

题目分析

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) 的时间复杂度，排序显然不行，所以自然想到用hash table。将序列中的所有数存到一个unordered_set中。对于序列里任意一个数A[i]，我们可以通过set马上能知道A[i]+1和A[i]-1是否也在序列中。如果在，继续找A[i]+2和A[i]-2，以此类推，直到将整个连续序列找到。为了避免在扫描到A[i]-1时再次重复搜索该序列，在从每次搜索的同时将搜索到的数从set中删除。直到set中为空时，所有连续序列搜索结束。

代码

import java.util.*;

public class Solution {
    public int longestConsecutive(int[] num) {
        if(num == null) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for(int item : num) {
            set.add(item);
        }
        int ans = 0;
        for(int item : num) {
            if(set.contains(item)) {
                set.remove(item);
                int l = item - 1;
                int r = item + 1;
                while(set.contains(l)) {
                    set.remove(l);
                    l --;
                }
                while(set.contains(r)) {
                    set.remove(r);
                    r++;
                }
                // ans = Math.max(ans, r - l + 1 - 2);
                ans = Math.max(ans, r - l - 1);
            }
        }
        return ans;
    }
}