# 128. Longest Consecutive Sequence

## 刷题内容

• https://leetcode.com/problems/longest-consecutive-sequence/

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.


class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(!nums.size())
return 0;
sort(nums.begin(),nums.end());
auto end_pos = unique(nums.begin(),nums.end());
int j = end_pos - nums.begin();
int ans = 1,sum = 1;
for(int i = 1;i < j;++i)
{
if(nums[i] == nums[i - 1] + 1)
sum++;
else
sum = 1;
ans = max(ans,sum);
}
return ans;
}
};


class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(!nums.size())
return 0;
unordered_map<int,int> m;
for(int i = 0;i < nums.size();++i)
m[nums[i]] = 0;
int ans = 0;
for(int i = 0;i < nums.size();++i)
{
if(m[nums[i]])
continue;
m[nums[i]] = 1;
int temp = nums[i] + 1,sum = 0;
while(m.find(temp) != m.end())
m[temp++] = 1;
sum = temp - nums[i];
temp = nums[i] - 1;
//cout << temp << endl;
while(m.find(temp) != m.end())
m[temp--] = 1;
sum += (nums[i] - temp - 1);
ans = max(ans,sum);
}
return ans;
}
};


apachecn/AiLearning