[LintCode] 124 Longest Consecutive Sequence 解题报告

Description
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.



Clarification
Your algorithm should run in O(n) complexity.



Example
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.



思路
先把数组里所有的元素全部倒进HashSet里。
遍历数组，对于每一个遍历到的元素，看HashSet里往上能走到哪里，往下能走到哪里。
同时，在check HashSet的时候，每找到一个，就从HashSet里把这个元素删掉。
这样，每遍历一个元素，就能找出包含这个元素的最大序列的长度。
因为我们一边还在HashSet里删除，所以不会重复计算。



Code

public class Solution {
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    public int longestConsecutive(int[] num) {
        // write you code here
        
        int max = 1;
        HashSet<Integer> set = new HashSet<>();
        
        for (int i = 0; i < num.length; i++) {
            set.add(num[i]);
        }
        
        for (int i = 0; i < num.length; i++) {
            int count = 1;
            int up = num[i] + 1;
            int down = num[i] - 1;
            while (set.contains(up)) {
                count++;
                set.remove(up);
                up++;
            }
            while (set.contains(down)) {
                count++;
                set.remove(down);
                down--;
            }
            max = Math.max(max, count);
        }
        
        return max;
    }
}