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.

Solution: use two hash tables to map a number to its longest sequence starting and ending at this number. Update the entries when you find numbers which are one more or one less than the current number in the table. Update the length of the interval as max.

Java语言: Longest Consecutive Sequence

01 public int longestConsecutive(int[] num) {
02     if(num.length<=1)
03         return num.length;
04     int max=1;
05     //Maps this number to the sequence start by this value;
06     Hashtable<Integer,Integer> start=new Hashtable<Integer,Integer>();
07     //Maps this number to the sequence end by this value;
08     Hashtable<Integer,Integer> end=new Hashtable<Integer,Integer>();
09     for(int i=0;i<num.length;i++)
10     {
11         //skip the number that has already seen
12         if(start.containsKey(num[i]))
13             continue;  
14       
15         start.put(num[i],1);
16         end.put(num[i],1);
17 
18         int lowerBound=num[i];          
19         int upperBound=num[i];
20       
21         //check the interval ending by its prev number
22         //get the lower bound that can be reached from the current  number
23         if(end.containsKey(num[i]-1))
24         {
25             lowerBound=num[i]-1-end.get(num[i]-1)+1;
26           
27         }
28         //check the interval starting from its next number
29         //get the upper bound that can be reached from the current number
30         if(start.containsKey(num[i]+1))
31         {
32             upperBound=num[i]+1+start.get(num[i]+1)-1;
33           
34         }
35         //update the interval
36         int range=upperBound-lowerBound+1;          
37         start.put(lowerBound, range);
38         end.put(upperBound, range);
39       
40         if(range>max)
41             max=range;          
42     }
43     return max;
44 }