128. Longest Consecutive Sequence

The basic idea is using a hashtable to record whether the consecutive number exist in the array. To do so, we need to traverse the array twice.

At the first round, we save the element of the array in a HashSet set.

At the second round, each time we traverse a element nums[i] existing in the set, we first remove nums[i] from set and then judge whether its consecutive numbers (nums[i] +k and nums[i] - k) exist in set. Here, k begins at 1 and increase by 1 if consecutive numbers exist in set.

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<Integer>();
    for(int i = 0; i < nums.length; i++)
	set.add(nums[i]);
    int max = 0;
    for(int i = 0; i < nums.length; i++) {
	if( !set.contains(nums[i]) )
	    continue;
	set.remove(nums[i]);
	int prev = nums[i] - 1, large = nums[i] + 1;
	while( set.contains(prev) ) {
	    set.remove(prev);
	    prev--;
	} 
	while( set.contains(large) ) {
	    set.remove(large);
	    large++;
	}
	max = Math.max(max, large - prev - 1);
    }
    return max;
}