128. 最长连续序列

为保证权益，题目请参考 128. 最长连续序列(From LeetCode).

解决方案1

CPP

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution
{
public:
    int longestConsecutive(vector<int> &nums)
    {
        unordered_set<int> sets;
        for (int i = 0; i < nums.size(); ++i)
        {
            sets.insert(nums[i]);
        }

        int ans = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (sets.find(nums[i] - 1) != sets.end())
            {
                int cur = nums[i];
                int len = 1;

                while (sets.find(cur + 1) != sets.end())
                {
                    cur += 1;
                    len += 1;
                }

                ans = max(ans, len);
            }
        }

        return ans;
    }
};

int main()
{
    vector<int> vec;
    vec.push_back(100);
    vec.push_back(4);
    vec.push_back(200);
    vec.push_back(1);
    vec.push_back(3);
    vec.push_back(2);

    Solution so;
    cout << so.longestConsecutive(vec) << endl;
    return 0;
}

Python

from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        dict1 = set(nums)
        res = 1
        for num in nums:
            if num-1 in dict1:
                continue
            if num+1 in dict1:
                ans = 2
                t = num + 1
                while t + 1 in dict1:
                    ans += 1
                    t += 1
                res = max(res, ans)
        return res