原题链接： Leetcode 128. 最长连续序列

C++ 解法1: map

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int res = 1;
        map<int,int> mp;
        for(auto x:nums) mp[x]=1;
        int pre=INT_MIN,cnt=0;
        for(auto x: mp){
            if(pre==INT_MIN || x.first==pre+1 ) {
                cnt++;
            }
            else{
                res = max(res,cnt);
                cnt=1;
            }
            pre = x.first;
        }
        return max(res,cnt);
    }
};

C++ 解法2: unordered_set

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size()==0) return 0;
        unordered_set<int> s;
        for(auto x: nums) s.insert(x);
        int res =0;
        for(int x: s){
            // 如果x不是某连续序列的起点
            if(s.contains(x-1)){
                continue;
            }
            int y = x+1;
            while(s.contains(y)){
                y++;
            }
            res = max(y-x,res);
        }
        return res;
    }
};

C++时间复杂度对比

• 解法 1：时间复杂度为 O(n log n)
  因为 map 的插入操作是 O (log n)，n 个元素总插入时间为 O (n log n)。
  后续遍历是 O (n)，整体受限于排序步骤，不满足题目要求的 O (n) 时间复杂度。
• 解法 2：时间复杂度为 O(n)
  unordered_set 的插入和查找都是 O (1)（平均情况）。
  每个元素最多被访问 2 次（一次作为起点遍历，一次被其他起点检查），整体为 O (n)，满足题目要求。

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)
        res = 0 
        for x in nums_set:
            if x -1 not in nums_set:
                y = x+1
                while y in nums_set:
                    y+=1
                res = max(res, y-x)
        return res

Java

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int res = 0;
        for(int x: nums) set.add(x);
        for(int x: set){
            if(!set.contains(x-1)){
                int y = x+1;
                while(set.contains(y)) y++;
                // 求最大
                res = Math.max(res,y-x);
            }
        }
        return res;
    }
}