面试经典150题 P128 最长连续序列

---

时间轴

时间轴

2025-11-14

init

哈希表

---

题目：

P128 最长连续序列

https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150

用哈希表，虽然是 for 循环里面一个 while，但是整体来看每个元素只访问了一次。核心思想是每次找到连续序列的最小值，然后依次找这个连续序列后面的连续元素。注意遍历时要按 uset 遍历，避免遍历 nums 时重复元素太多。

#include <vector>
#include <unordered_set>

using std::unordered_set;
using std::vector;

class Solution {
    public:
        int longestConsecutive(vector<int> &nums)
        {
                int curr, longest = 0;
                unordered_set<int> uset(nums.begin(), nums.end());
                for (auto &num : uset) {// 遍历uset,避免遍历nums时重复元素太多
                        if (!uset.count(num - 1)) { // 连续序列中最小的那个
                                curr = 1;
                                while (uset.count(num + curr)) {
                                        curr++;
                                }
                                longest = std::max(longest, curr);
                        }
                }
                return longest;
        }
};

也可以找一个序列中最大的那个：

#include <vector>
#include <unordered_set>
#include <algorithm>
using std::vector;
using std::unordered_set;

class Solution {
    public:
        int longestConsecutive(vector<int> &nums)
        {
                unordered_set<int> uset(nums.begin(), nums.end());

                int n = nums.size();
                int cnt, max_val = 0;                

                // 先找到序列的终点
                for (int curr : uset) {
                        if (uset.count(curr + 1) != 0)
                                continue;
                        
                        // curr 现在是一个连续序列的最后一个元素
                        cnt = 1;
                        while (uset.count(curr - cnt) != 0)
                                cnt++;
                        max_val = std::max(max_val, cnt);
                }
                return max_val;
        }
};