solution.md

# 最长连续序列

<p>给定一个未排序的整数数组 <code>nums</code> ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。</p>

<p>请你设计并实现时间复杂度为 <code>O(n)</code><em> </em>的算法解决此问题。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>nums = [100,4,200,1,3,2]
<strong>输出：</strong>4
<strong>解释：</strong>最长数字连续序列是 <code>[1, 2, 3, 4]。它的长度为 4。</code></pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>nums = [0,3,7,2,5,8,4,6,0,1]
<strong>输出：</strong>9
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>0 <= nums.length <= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>
</ul>

<p>以下<font color="red">错误</font>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after

```cpp
int main()
{
    Solution sol;
    int res;
    vector<int> vec = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
    res = sol.longestSequence(vec);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int longestConsecutive(vector<int> &nums)
    {
        unordered_set<int> hash;
        for (const int &num : nums)
        {
            hash.insert(num);
        }
        int ans = 0;
        while (!hash.empty())
        {
            int cur = *(hash.begin());
            hash.erase(cur);
            int next = cur + 1, prev = cur - 1;
            while (hash.count(next))
            {
                hash.erase(next++);
            }
            while (hash.count(prev))
            {
                hash.erase(prev--);
            }
            ans = max(ans, next - prev);
        }
        return ans;
    }
};
```
## 选项

### A
```cpp

class Solution
{
public:
    int longestConsecutive(vector<int> &nums)
    {
        unordered_map<int, int> mp;
        int l = 0, r = 0, res = 0, len = 0;
        for (int num : nums)
        {
            if (!mp[num])
            {
                l = mp[num - 1];
                r = mp[num + 1];
                len = l + r + 1;
                res = max(res, len);
                mp[num] = len;
                mp[num - l] = len;
                mp[num + r] = len;
            }
        }
        return res;
    }
};
```

### B
```cpp
class Solution
{

    struct DisJointSet
    {
        vector<int> _id;
        vector<int> _size;
        int max_size;
        int _count;
        DisJointSet(int Num)
        {
            for (int i = 0; i < Num; i++)
            {
                _id.emplace_back(i);
                _size.emplace_back(1);
            }
            _count = Num;
            max_size = 1;
        }

        int find_(int p)
        {
            while (p != _id[p])
            {
                _id[p] = _id[_id[p]];
                p = _id[p];
            }
            return p;
        }

        void _union(int p, int q)
        {
            int i = find_(p);
            int j = find_(q);
            if (i == j)
                return;
            if (_size[i] > _size[j])
            {
                _id[j] = i;
                _size[i] += _size[j];
                max_size = max(max_size, _size[i]);
            }
            else
            {
                _id[i] = j;
                _size[j] += _size[i];
                max_size = max(max_size, _size[j]);
            }
            _count--;
        }
    };

public:
    int longestConsecutive(vector<int> &nums)
    {
        if (nums.size() == 0)
            return 0;
        DisJointSet disJointSet(nums.size());
        unordered_set<int> nums_set;
        unordered_map<int, int> nums_disJointSetID_map;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums_set.find(nums[i]) != nums_set.end())
                continue;
            nums_set.insert(nums[i]);
            nums_disJointSetID_map[nums[i]] = i;
            if (nums_set.find(nums[i] - 1) != nums_set.end())
            {
                disJointSet._union(nums_disJointSetID_map[nums[i]], nums_disJointSetID_map[nums[i] - 1]);
            }
            if (nums_set.find(nums[i] + 1) != nums_set.end())
            {
                disJointSet._union(nums_disJointSetID_map[nums[i]], nums_disJointSetID_map[nums[i] + 1]);
            }
        }
        return disJointSet.max_size;
    }
};
```

### C
```cpp
class Solution
{
public:
    int longestConsecutive(vector<int> &vec)
    {
        set<int> s;
        for (int elem : vec)
            s.insert(elem);

        int longest = 0;
        int cnt = 1;
        for (auto e : s)
        {
            if (s.find(e + 1) != s.end())
            {
                cnt++;
            }
            else
            {
                cnt = 1;
            }
            longest = max(longest, cnt);
        }
        return longest;
    }
};
```