LeetCode 128. Longest Consecutive Sequence（最長連續序列）

原題網址：https://leetcode.com/problems/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.

方法：通過哈希集合快速定位。

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Set<Integer> numSet = new HashSet<>();
        for(int num: nums) numSet.add(num);
        int max = 1;
        while (!numSet.isEmpty()) {
            int range = 1;
            int num = numSet.iterator().next();
            numSet.remove(num);
            for(int i=1; ; i++) {
                if (numSet.remove(num+i)) range ++;
                else break;
            }
            for(int i=1; ; i++) {
                if (numSet.remove(num-i)) range ++;
                else break;
            }
            max = Math.max(max, range);
        }
        return max;
    }
}