M128.最长连续序列

hash table, union find, https://leetcode.cn/problems/longest-consecutive-sequence/

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

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

示例 1：

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

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

哈希+起点法

python

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if not nums:
            return 0

        s = set(nums)
        max_len = 0

        for num in s:
            # 只有当 num 是连续序列的起点时才扩展
            if num - 1 not in s:
                cur = num
                length = 1
                while cur + 1 in s:
                    cur += 1
                    length += 1
                max_len = max(max_len, length)

        return max_len

并查集

python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            # 小集合并到大集合
            if self.size[rx] < self.size[ry]:
                rx, ry = ry, rx
            self.parent[ry] = rx
            self.size[rx] += self.size[ry]


class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if not nums:
            return 0

        # 去重后编号映射
        nums = list(set(nums))
        n = len(nums)
        idx = {num: i for i, num in enumerate(nums)}

        uf = UnionFind(n)

        # 合并相邻的数字
        for num in nums:
            if num + 1 in idx:
                uf.union(idx[num], idx[num + 1])

        # 最大集合大小
        return max(uf.size)

思路：区间合并法，类似于合并区间的“线段并法”。用字典记录“区间的左右边界长度”，例如：

当加入一个新数 x 时：
- 若左右都没有连续的数，则新建 [x, x]；
- 若左边有连续数（x-1），则合并到左边；
- 若右边有连续数（x+1），则合并到右边；
- 若左右都有，则连接两个区间；
同时更新区间端点的长度信息。

这是一种 哈希 + 动态合并区间 的写法，核心思想是“只维护区间两端的长度信息”。

python

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        s = {}
        longest = 0

        for x in nums:
            if x in s:  # 跳过重复
                continue

            left = s.get(x - 1, 0)
            right = s.get(x + 1, 0)
            length = left + right + 1
            s[x] = length

            # 更新左右边界的长度信息
            s[x - left] = length
            s[x + right] = length

            longest = max(longest, length)

        return longest

举例：

输入 [100, 4, 200, 1, 3, 2]

插入 1：{1:1} → longest=1
插入 2：连接左边 → {1:2, 2:2}
插入 3：连接左边 → {1:3, 3:3, 2:2}
插入 4：→ {1:4, 4:4, 3:3, 2:2}
插入 100、200 不影响最长长度。

最终 longest = 4。

M128.最长连续序列 ​

M128.最长连续序列