# longest consecutive sequence

## longest consecutive sequence

### Seems hard

This problem looks hard, and I did not find any pretty solutions. The book 《creaking the coding interview》has a famous saying:"heashtable may help you.". Put all element in a map, then for each in the vector figure out the left an d right length. When search left and right element, we can erase the element which already searched by us, and this limited the time complexity to O(n).

`````` 1 class Solution {
2 public:
3     int longestConsecutive(vector<int> &num) {
4         int n = num.size();
5         if ( 0 == n ) {
6             return 0;
7         }
8         map< int, int > numMap;
9         for ( int i = 0; i < n; i++ ) {
10             numMap[num[i]] = 1;
11         }
12         int result = 0;
13         for ( int i = 0; i < n; i++ ) {
14             int t = num[i];
15             int now = 0;
16             if ( numMap.find(t) != numMap.end() ) {
17                 numMap.erase(t);
18                 now = 1;
19                 int left = t-1;
20                 while( numMap.find(left) != numMap.end() ) {
21                     numMap.erase(left);
22                     left--;
23                     now++;
24                 }
25                 int right = t+1;
26                 while ( numMap.find(right) != numMap.end() ) {
27                     numMap.erase(right);
28                     right++;
29                     now++;
30                 }
31             }
32             result = max(result,now);
33         }
34         return result;
35     }
36 };``````