LeetCode 热题 100 | 128. 最长连续序列

🚀 题目描述

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

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

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

You must write an algorithm that runs in O(n) time.

Example 1:

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

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

核心逻辑：触点合并

想象数组中的每个数字都是一个独立的点。当我们把 num 放入集合时，它就像一根“导线”，试图连接左右两个已经存在的“通区间”。

1. 左顾右盼：
   • 检查 num - 1 是否存在？若存在，获取其所在区间的长度 prev。
   • 检查 num + 1 是否存在？若存在，获取其所在区间的长度 suf。
2. 瞬间合体：
   • 当前数字 num 加入后，形成的全新区间长度为：
   len = prev + suf + 1
3. 刷新边界：
   • 我们并不需要更新区间内所有点的长度，只需要更新该区间的“最左端”和“最右端”。因为新加入的数字只会从边缘撞击该区间。

---

💻 代码实现 (C++)

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        // cnt 存储当前数值所在连续区间的总长度
        unordered_map<int, int> cnt;

        for (int& num : nums) {
            // 跳过重复数字，确保每个点只被处理一次
            if (cnt.find(num) == cnt.end()) {
                // 1. 获取左右邻居的区间长度
                int prev = cnt.count(num - 1) ? cnt[num - 1] : 0;
                int suf = cnt.count(num + 1) ? cnt[num + 1] : 0;

                // 2. 计算当前合并后的新区间总长度
                int cur_len = prev + suf + 1;
                
                // 3. 标记当前点已访问，并同步更新区间的左右端点
                cnt[num] = cur_len; 
                cnt[num - prev] = cur_len; // 指向左边界
                cnt[num + suf] = cur_len;  // 指向右边界

                // 4. 实时更新最大值
                ans = max(ans, cur_len);
            }
        }
        
        return ans;
    }
};

📊 复杂度分析

时间复杂度

T(n) = O(n)

由于 unordered_map 的操作平均为常数时间，且通过 if 逻辑确保了每个数字仅被处理一次，整段代码实现了真正的线性扫描。

空间复杂度

S(n) = O(n)

最坏情况下，哈希表需要存储所有不重复的数字。