# 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 };
```