124 · Longest Consecutive Sequence - LintCode

# Description

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

You must write an algorithm that runs in O(n) time.

# Example

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

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

# Code

找當前數的前一個和後一個，若存在，從 set 裡 remove

	class Solution {
	public int longestConsecutive(int[] nums) {
	if (nums == null \|\| nums.length == 0) return 0;
	Set<Integer> set = new HashSet<>();
	for (int num: nums) {
	set.add(num);
	}

	int prev;
	int next;
	int max = 0;
	for (int i = 0; i < nums.length; i++) {
	prev = nums[i] - 1;
	next = nums[i] + 1;

	while (set.contains(prev)){
	set.remove(prev);
	prev--;
	}
	while (set.contains(next)) {
	set.remove(next);
	next++;
	}
	max = Math.max(max, next - prev - 1);
	}
	return max;
	}
	}