128.longest-consecutive-sequence.py

#
# @lc app=leetcode id=128 lang=python3
#
# [128] Longest Consecutive Sequence
#
# Difficulty: Medium
# Frequency: 89.7%
# Tags: Array, Hash Table, Union-Find
# URL: https://leetcode.com/problems/longest-consecutive-sequence/
#
# --- Problem Description ---
#
# 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 <= 10^(5)
# 	  - -10^(9) <= nums[i] <= 10^(9)
#

#
# --- Community Solutions ---
#
# https://leetcode.com/problems/longest-consecutive-sequence/solutions
#

# Hash Set / 起点检测 - O(n) time, O(n) space
#
# 清单定位：
#   常用数据结构 / 哈希与集合，rank #19。
#   主干是：set 判序列起点，只从起点向右扩展。
#
# 这题其实在做什么：
#   给一个无序数组，找最长的连续整数链，比如 1,2,3,4 的长度是 4。
#   题目强制 O(n)，所以重点不是"能不能找出来"，而是不能排序后再扫。
#
# 识别信号：
#   - "longest consecutive sequence" -> 连续整数链
#   - "unsorted" + "O(n)" -> 不能排序，优先想 hash set
#   - 只关心值是否存在，不关心原始顺序 -> set 比数组扫描更适合
#
# 为什么排序不够：
#   排序后扫一遍很直观，但排序是 O(n log n)，不满足题目要求的 O(n)。
#   暴力从每个数开始往后找更糟，在 [1,2,3,...,n] 上会重复扩展很多次。
#
# 核心思路：
#   先把所有数字放进 lookup_set，获得 O(1) 平均时间的存在性查询。
#   然后只从"序列起点"开始数长度：
#   - 如果 num - 1 在 set 里，num 不是起点，跳过。
#   - 如果 num - 1 不在 set 里，num 是某条连续链的最小值，从 num+1 往右扩展。
#
#   关键是"只从起点扩展"：每条连续链只会被它的最小值负责数一次。
#   非起点只做一次 O(1) 检查，所以总工作量仍然是 O(n)。
#
# 跑例：nums = [100, 4, 200, 1, 3, 2]
#
#   lookup_set = {1, 2, 3, 4, 100, 200}
#
#   num=1:   0 不在 set -> 起点，数 1,2,3,4，长度 4
#   num=2:   1 在 set   -> 不是起点，跳过
#   num=3:   2 在 set   -> 不是起点，跳过
#   num=4:   3 在 set   -> 不是起点，跳过
#   num=100: 99 不在 set -> 起点，长度 1
#   num=200: 199 不在 set -> 起点，长度 1
#   答案 = 4
#
# 关键状态 / 不变量：
#   lookup_set = 所有不同数字，用来 O(1) 判断某个值是否存在。
#   max_seq_len = 目前见过的最长连续链长度。
#   不变量：只有 num - 1 不存在时，num 才会启动一次向右扩展。
#   因此同一条链不会从中间节点重复计数。
#
# 边界条件 / 边界调节：
#   - 空数组：lookup_set 为空，循环不进入，返回 0。
#   - 重复数字：必须用 set 去重，并遍历 lookup_set；否则重复的起点会重复扩展。
#   - 负数也正常，因为连续性只看 num + 1 是否存在。
#
# 最小反例 / 易错例：
#   nums = [1, 1, 1, 2]
#   如果遍历原数组 nums，三个 1 都会各自扩展到 2，虽然答案仍对，但工作重复，
#   破坏题目要求的 O(n) 思路。遍历 lookup_set 后，只会处理一个 1。
#
# 落码步骤 / 伪代码骨架：
#   1. lookup_set = set(nums)，max_seq_len = 0。
#   2. 遍历 lookup_set 中的每个 num。
#   3. 如果 num - 1 在 lookup_set，说明 num 不是起点，跳过。
#   4. 否则从 tail = num + 1 开始 while tail in lookup_set，持续累加长度。
#   5. 用当前链长度更新 max_seq_len。
#
# 复杂度：
#   - 时间 O(n)：建 set 是 O(n)；每个数字最多作为一次链的一部分被向右数到。
#   - 空间 O(n)：lookup_set 最多保存 n 个不同数字。
#
# 什么不变 / 什么变了：
#   - 和 Two Sum 一样，核心都是把"值是否出现过"交给哈希结构。
#   - Two Sum 查的是 target - x；本题查的是 num - 1 和 num + 1。
#
# 一句模板：
#   最长连续序列 -> set 去重，只从没有前驱 num-1 的起点开始向右数。
#
# 记忆锚点：
#   "找链头，不找链中间"；链头负责整条链，中间节点只负责跳过。
#
# 主动回忆检查：
#   - 为什么判断 num - 1 不存在就能确认 num 是链头？
#   - 如果遍历 nums 而不是 lookup_set，重复数字会怎样影响复杂度？

# @lc code=start
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # lookup_set 提供 O(1) 平均查询，也顺手去掉重复数字。
        lookup_set = set(nums)
        max_seq_len = 0

        # FIX: 遍历 lookup_set 而不是 nums，避免重复起点反复扩展同一条链。
        for num in lookup_set:
            # 只有没有前驱的数字才是链头；非链头跳过，保证每条链只数一次。
            if num - 1 not in lookup_set:
                seq_len = 1
                tail = num + 1

                # 从链头向右扩展，直到下一个连续数字不存在。
                while tail in lookup_set:
                    seq_len += 1
                    tail += 1
                max_seq_len = max(seq_len, max_seq_len)

        return max_seq_len


# @lc code=end