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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public: int longestConsecutive(vector<int> &num) { unordered_map<int,int> m; int ans = 0; for(auto n : num) { if(m.count(n)) continue; if(m.count(n-1) && m.count(n+1)){ int l = m[n-1], r = m[n+1]; m[n] = m[n-l] = m[n+r] = r+l+1; } else if(m.count(n-1)) { int l = m[n-1]; m[n] = m[n-l] = l+1; } else if(m.count(n+1)) { int r = m[n+1]; m[n] = m[n+r] = r+1; } else { m[n] = 1; } ans = max(ans, m[n]); } return ans; } }; |