128. 最长连续序列

LeetCode 128¹ · 中等 · 哈希

题

给一个未排序的整数数组，求数值上连续的数字（不要求在数组里相邻）最长能连成多长。要求 \(O(n)\)。

例：[100, 4, 200, 1, 3, 2] → 4（1, 2, 3, 4）。

一句话

丢进 set，只在 x - 1 不存在时从 x 开始往上数——每条连续段只被数一遍。

关键技巧

排序是 \(O(n \log n)\)，题目卡死了 \(O(n)\)，所以只能靠哈希的 \(O(1)\) 查询。 最朴素的想法是对每个 x 都往上查 x+1, x+2, …，但段内每个数都当一次起点，最坏退化到 \(O(n^2)\)（比如 1..n）。

只从起点出发。 x 是某条连续段的起点，当且仅当 x - 1 不在集合里。只对起点往上数，那么每条段恰好被完整走一次，所有段长之和 \(\le n\)；加上外层对每个数做一次 \(O(1)\) 的起点判断，总共 \(O(n)\)。

遍历 set 而不是原数组。 原数组有重复值时，同一个起点会被重复展开——[1, 1, 1, …, 1, 2, 3, …] 这种输入会让遍历数组退化；遍历去重后的 set 就没有这个问题。

解

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        best = 0
        for x in s:
            if x - 1 in s:  # 不是起点，交给起点去数
                continue
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
        return best

时间 \(O(n)\)，空间 \(O(n)\)。

延伸

• 和 1. 两数之和 同骨架：都是「查某个值在不在集合里」，这里查的是 x - 1 和 x + 1。
• 另一种写法是并查集，把 x 和 x + 1 合并，最后取最大分量；同样近似 \(O(n)\)，但常数大、代码长。
• 若要支持动态插入，可以用哈希表只在段的两个端点存段长：插入 x 时读 left = len[x-1]、right = len[x+1]，新段长 left + right + 1 写回两端。

s = Solution()
assert s.longestConsecutive([100, 4, 200, 1, 3, 2]) == 4
assert s.longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9
assert s.longestConsecutive([1, 0, 1, 2]) == 3
assert s.longestConsecutive([]) == 0
assert s.longestConsecutive([-1, -2, 5]) == 2