Longest Consecutive Sequence

Question

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

Your algorithm should run in O(n) complexity.

Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

LeetCodeleetcode.com/problems/longest-consecutive-sequence

Solution

/*
@param: int[]
@return: int
放到set里面，然后遍历检查每一个数的+1，-1是否存在，存在则remove。记录每一个序列up和down即可，求max
*/
public int longestConsecutive(int[] nums) {
    if (nums.length <= 1) {
        return nums.length;
    }
    
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        set.add(nums[i]);
    }
    
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        int up = nums[i];
        while (set.contains(up)) {
            set.remove(up);
            up++;
        }
        
        int down = nums[i]-1;
        while (set.contains(down)) {
            set.remove(down);
            down--;
        }
        result = Math.max(result, up-down-1);
    }
    return result;
}