哈希

模板一：存在性判断与去重 (使用 set)

1. 题型雷达（什么时候该条件反射想到 Set？）

不要一看到“数组”就想到 for 循环。当面试题目的描述中出现以下组合信号时，你的“Set 雷达”必须立刻狂响：

• 信号一：关键词提示。 题目中明确包含“是否存在 (contains)”、“去重 (unique/duplicate)”、“交集/并集 (intersection)”。
• 信号二：时间复杂度锁死 $O(N)$，且数组无序。 这是一个非常强烈的暗示！如果数组无序，你想找某个特定的关联元素，暴力找是 $O(N^2)$；排序后再用二分找是 $O(N \log N)$。面试官如果明确要求 $O(N)$，排序这条路就被堵死了，唯一的出路就是用空间换时间，祭出 Hash 结构。如果没有复杂的键值映射关系，首选就是 set。
• 信号三：需要频繁执行 if x in collections: 操作。 * 新手易错点： 在 Python 中，如果用 if x in list，底层需要遍历整个列表，时间复杂度是 $O(N)$。
  • 老手操作： 只要发现代码里有频繁的 in 判断，马上把 list 转成 set，if x in set 的时间复杂度是 $O(1)$。这是质的飞跃。

---

2. 模板熟练度（刻在 DNA 里的肌肉记忆）

Python 3 操作 set 的代码极其简洁，但你需要熟练掌握以下两种标准范式：

范式 A：边遍历边判断（防止自己和自己匹配）

用于寻找某种配对关系，或者第一次遇到重复元素时就返回。

Python

seen = set()
for num in nums:
    # 查找逻辑写在加入 set 之前，确保是和历史元素比较
    if 满足某种条件的衍生物(num) in seen: 
        return True 
    seen.add(num)
return False

范式 B：全量预处理（用于全局视角的查找）

当你需要在一个完整的无序集合中到处“乱跳”查找时，先一把梭哈转成 set。

Python

# $O(N)$ 时间复杂度，直接转为哈希集合
num_set = set(nums) 
for num in num_set:
    # 此时内部如果有 num + 1, num - 1 等查找操作，都是 $O(1)$
    if num + 1 in num_set: 
        # do something

---

3. 变形能力（大厂实战：最长连续序列）

只懂基础去重是拿不到 Offer 的。我们直接拿 Hot 100 里的 LeetCode 128: 最长连续序列 (Longest Consecutive Sequence) 来实战演练你的变形能力。

题目大意： 给定一个未排序的整数数组 nums ，找出数字连续的最长序列的长度。要求时间复杂度为 $O(N)$。

• 输入：nums = [100, 4, 200, 1, 3, 2]
• 输出：4 （最长连续序列是 [1, 2, 3, 4]）

【思维突破过程】

1. 雷达触发： “未排序” + “找序列” + 强制要求 “$O(N)$ 时间”。直接排除先排序再找的 $O(N \log N)$ 解法。必须用哈希表。只需要知道元素存不存在，所以用 set，对应模板范式 B。
2. 生搬硬套（错误示范）： 新手可能会想，我把所有数放进 set，然后遍历每个数，向右一直找它后面的数存在不存在。
   • 伪代码： 针对 1 找 2,3,4；针对 2 找 3,4；针对 3 找 4。
   • 致命问题： 这里面包含了大量的重复工作！如果数组就是 [1,2,3,4,5,6]，你会把每个数字后面的序列都查一遍，最坏情况退化成了 $O(N^2)$，面试直接挂。
3. 变形能力（看透本质）： 我们怎么避免重复劳动？只从序列的“起点”开始向后找！
   • 怎么判断一个数是不是“起点”？如果 num - 1 不在 set 里，那 num 就是一个序列的开头！
   • 如果是 2，因为 1 在 set 里，所以 2 不是开头，直接跳过！

【Python 3 满分代码】

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums) # $O(N)$ 建立哈希集合

        for num in num_set:
            # 核心变形逻辑：只在确认是“序列起点”时才开始循环匹配
            if num - 1 not in num_set: 
                current_num = num
                current_streak = 1

                # 顺藤摸瓜，因为是 set，这里的查找是 $O(1)$
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

面试官大概率会追问的灵魂一击：

“你的代码里明明写了一个 for 循环，里面还套了一个 while 循环，你凭什么说你的时间复杂度是 $O(N)$，而不是 $O(N^2)$？”

作为我的学生，你应该这样霸气（但礼貌地）回答：

“因为有 if num - 1 not in num_set 这个终极卡口。只有当元素是序列的第一个数字时，才会进入 while 循环。这意味着数组中的每个元素，最多只会被外层 for 循环访问一次，在内层 while 循环匹配时被访问一次。总体来说，每个元素最多被访问两次，时间复杂度依然是严格的 $O(N)$。”

求交集在 Python 中应该用“按位与”（& 操作符）或者 .intersection() 方法，而不是“相减”。“相减”（- 操作符）求的是差集（找在 A 里但不在 B 里的元素）

模板二：映射关系与索引记录 (使用 dict)

1. 题型雷达（什么时候必须掏出 dict？）

当你读题时，一旦发现不仅要找某个元素“存不存在”，还必须知道关于它的附加信息时，雷达就要锁定 dict：

• 雷达信号一：要求返回索引（Index）。 题目不仅问有没有，还问在哪儿。比如经典的“两数之和”。
• 雷达信号二：需要统计频次（Frequency/Count）。 题目出现了“出现次数最多”、“超过一半的数字”、“频次排序”等字眼。
• 雷达信号三：需要归类/分组（Group by）。 题目要求把具有某种相同特征的元素放在一起。
• 雷达信号四：配对查找（Complement）。 知道 A，要去找特定的 B（比如 $B = \text{target} – A$）。

---

2. 模板熟练度（“边查边存”的艺术）

在操作 dict 时，新手最容易犯的错误是：习惯性地先用一个 for 循环把所有东西塞进字典，然后再用一个 for 循环去查。 这虽然不影响 Big-O 的时间复杂度（依然是 $O(N)$），但需要遍历两次。在大厂面试中，追求极致的“一次遍历（One-pass）”才是满分答卷。

黄金模板：边遍历，边查找，边记录

Python

# 初始化哈希表
hash_map = {} 

for i, num in enumerate(nums):
    # 1. 计算当前元素需要的“配对目标”
    target = 某种运算(num) 
    
    # 2. 去历史记录里查，目标是否已经存在？
    if target in hash_map:
        # 找到了！返回当前索引和目标之前存下的值
        return [hash_map[target], i] # 或者做其他处理
        
    # 3. 没找到？把当前元素和它的附加信息（如索引）存入字典，供后面的兄弟查找
    hash_map[num] = i 

这个模板的精髓在于“时间差”。每次检查 hash_map 时，里面只包含当前元素左边的元素。这天然地避免了“自己和自己匹配”的尴尬情况！

---

3. 变形能力（从“两数之和”到“异位词分组”）

我们来看看同一个 dict 思想，在 Hot 100 中是如何变形出不同难度的题目的。

变形一：基础查找（LeetCode 1: 两数之和）

• 需求： 找 $a + b = \text{target}$，返回索引。
• 映射关系： Key = 数字的值，Value = 该数字的索引。
• 应用模板： 就是上面的黄金模板，target = target - num。这是必须达到“肌肉记忆”、闭着眼睛都能敲出来的级别。

变形二：特征分组（LeetCode 49: 字母异位词分组）

这道题是考察变形能力的试金石。

• 题目大意： 给定一个字符串数组 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]，把字母相同但顺序不同的词（异位词）分到一组。
• 思维突破： 既然要把它们分到一组，它们必须共用同一个 Key。怎么让 "eat" 和 "tea" 生成相同的 Key 呢？
  • 思路 A（排序法）： 把字符串内部的字符按字母表排序，"eat" 和 "tea" 排序后都变成了 "aet"。
  • 思路 B（计数法）： 统计每个字母出现的频次，转成一个长度为 26 的 tuple 作为 Key。
• 映射关系： Key = 排序后的字符串（特征标识），Value = list（属于该特征的原始字符串列表）。

【Python 3 满分代码 – 异位词分组】

Python

import collections

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 使用 defaultdict，当 key 不存在时会自动初始化为一个空列表 []
        anagram_map = collections.defaultdict(list)
        
        for s in strs:
            # 变形核心：提炼共性特征作为 Key
            # sorted(s) 返回的是字符列表，必须用 "".join() 拼成字符串，或者转成 tuple，因为字典的 Key 必须是不可变类型 (hashable)
            key = tuple(sorted(s)) 
            
            # 将原始字符串追加到对应的分类中
            anagram_map[key].append(s)
            
        # 返回字典中所有的 value（即所有分好组的列表）
        return list(anagram_map.values())

• 老师划重点： 在 Python 中，字典的 Key 必须是可哈希的（不可变类型）。所以你不能用 list 做 Key，必须转成 tuple 或者 str！这是面试官非常喜欢考察的 Python 基础细节。

模板三：进阶变形 —— 前缀和 + 哈希表 (Killer 级别)

第一层：看透本质 —— 什么是前缀和？为什么能和哈希表结合？

在讲模板之前，我们必须先在纸上推导一下。

所谓“前缀和”，就是数组从头开始累加的和。

假设数组是 nums，前缀和数组是 P，那么 P[i] 就表示从 nums[0] 加到 nums[i] 的总和。

核心数学公式：

任何一个连续子数组 nums[i...j] 的和，都可以用两个前缀和相减来表示：

$$Sum(i, j) = P[j] – P[i-1]$$

如果题目要求找一个连续子数组，它的和等于目标值 $K$，那么公式就是：

$$P[j] – P[i-1] = K$$

高能预警！下面是整套理论的灵魂变形：

在遍历数组时，我们当前站在索引 $j$ 的位置，P[j] 是我们刚刚算出来的当前前缀和，$K$ 是已知的目标值。我们需要知道，在 $j$ 之前，有没有出现过某个前缀和 P[i-1]，能满足上面的等式？

把公式移项：

$$P[i-1] = P[j] – K$$

看懂了吗？这瞬间变成了一个“两数之和（Two Sum）”问题！ 在“两数之和”里，我们用哈希表存走过的数字，找 Target - 当前数字。 在“前缀和”里，我们用哈希表存走过的历史前缀和，找 当前前缀和 - K！

---

1. 题型雷达（极其严苛的触发条件）

遇到以下三个条件的完美组合，直接默写这套模板：

• 雷达信号一：“连续子数组” (Subarray)。 注意，一定是“连续”的，不能是子序列（Subsequence）。
• 雷达信号二：“求和等于 K” 或者 “某种求和特征”。 比如和为特定值、被整除、或者 0 和 1 的数量相等。
• 雷达信号三：数组中包含负数！ （极其关键！）
  • 老师敲黑板： 如果数组全是非负数，求和等于 K，首选滑动窗口 (Sliding Window)，因为窗口扩大和一定增加，窗口缩小和一定减小，具有单调性。
  • 一旦数组里有负数，加一个负数和反而变小了，滑动窗口的单调性被破坏，滑动窗口直接失效，此时唯一的解法就是 前缀和 + 哈希表。

---

2. 模板熟练度（刻在骨子里的四步法）

这套模板的代码很短，但每一行都有深意。请仔细体会这里的 dict 到底存了什么。

Python

def subarraySum(nums: List[int], k: int) -> int:
    count = 0
    prefix_sum = 0
    
    # 核心初始化：字典的含义是 {前缀和的值: 该前缀和出现的次数}
    # 为什么要有 {0: 1}？这叫“虚拟前缀和”。
    # 代表在数组开始前，前缀和为 0 的情况已经发生了一次。
    # 如果没有这一行，任何从索引 0 开始的合法子数组都会被漏掉！
    hash_map = {0: 1} 
    
    for num in nums:
        # 1. 边走边累加，算出当前前缀和
        prefix_sum += num 
        
        # 2. 核心公式：回头找历史记录中，有没有需要的 P[i-1]
        target = prefix_sum - k 
        if target in hash_map:
            # 3. 注意！这里是加上它出现的次数，而不是 +1。
            # 因为如果有多个历史位置的前缀和相同，它们都能和当前位置组合成和为 K 的子数组
            count += hash_map[target] 
            
        # 4. 把当前的前缀和状态也记录进哈希表，供后面的元素查找
        hash_map[prefix_sum] = hash_map.get(prefix_sum, 0) + 1
        
    return count

---

3. 变形能力（大厂实战真题）

我们直接拿 Hot 100 里的原题和它的变体来测试你的变形能力。

基础形态：LeetCode 560. 和为 K 的子数组

这道题完全就是上面模板的默写。只要你懂了 target = prefix_sum - k，并且记得初始化 {0: 1}，这题在面试中就是送分题，你可以 3 分钟内 bug-free 写完，惊艳面试官。

进阶变形一：LeetCode 525. 连续数组 (0 和 1 数量相等)

• 题目大意： 给定一个二进制数组 nums（只包含 0 和 1），找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
• 雷达识别： “连续子数组” + “特征（0和1相等）”。但是没有明确的 $K$ 啊？
• 变形思维（Killer 级）： 怎么把“0和1数量相等”转化成“和为某个目标值”？
  • 神仙操作：把所有的 0 视作 -1！
  • 如果一段连续子数组里 0 和 1 的数量相等，那么把 0 变成 -1 后，这段子数组的总和等于几？等于 0！
  • 题目瞬间被我们转化成了：求和为 $K = 0$ 的最长连续子数组。
• 映射关系微调： 既然求的是“最长长度”而不是“个数”，哈希表里的 Value 就不再存“出现次数”了，而是存“该前缀和第一次出现的索引”，这样当前的索引减去历史索引，就能算出长度。

【变形伪代码一瞥】

Python

hash_map = {0: -1} # 初始化：前缀和为 0 的起始索引在 -1 位置
max_len = 0
prefix_sum = 0
for i, num in enumerate(nums):
    prefix_sum += 1 if num == 1 else -1
    if prefix_sum in hash_map: # K=0，所以 prefix_sum - 0 还是 prefix_sum
        max_len = max(max_len, i - hash_map[prefix_sum])
    else:
        hash_map[prefix_sum] = i # 只记录第一次出现的位置，为了保证长度最长

双指针

模板一：对撞指针 (Collision Pointers) —— 夹逼法则

1. 题型雷达（什么时候该亮出“夹逼”大招？）

面试中，当你读题时捕捉到以下信号，你的大脑应该立刻浮现出左右两端向中间靠拢的画面：

• 最强雷达：数组“已排序” + 寻找“组合/配对”。 这是最经典的触发条件。因为数组有序，所以大小关系是单调的。左边一定是小的，右边一定是大的。
• 雷达二：遇到“回文（Palindrome）”字眼。 回文串天然具有中心对称的属性，验证回文最直观的方法就是左指针指头，右指针指尾，向中间夹逼比对。
• 雷达三：需要“降维打击”的求和问题。 比如题目要求找三个数、四个数的和。暴力解法是 $O(N^3)$ 或 $O(N^4)$。这时候通常需要先对数组排序（耗费 $O(N \log N)$），然后固定一个或两个数，把剩下的部分变成“两数之和”，用对撞指针在 $O(N)$ 内解决。

---

2. 模板熟练度（刻在 DNA 里的骨架）

对撞指针的模板非常标准，但在细节上（比如 while 的条件）绝对不能写错。

黄金模板：左右夹逼法

Python

def collision_pointers(nums):
    # 1. 左右指针初始化在两端
    left = 0
    right = len(nums) - 1
    
    # 2. 核心循环条件：绝大多数情况是 left < right。
    # 为什么不是 left <= right？因为指针相遇指向同一个元素时，通常无法构成“一对”合法的组合。
    while left < right:
        current_state = 评估当前状态(nums[left], nums[right])
        
        if current_state == 目标状态:
            return 找到了合适的结果 # 或者记录结果，然后 left += 1, right -= 1 继续找
            
        elif current_state < 目标状态:
            # 3. 淘汰逻辑：如果当前状态偏小，且数组升序排列
            # 说明右指针即使和左指针右侧的所有数字组合都会偏小，右指针尽力了。
            # 只能让左指针向右移动，去寻找更大的值。
            left += 1
            
        else:
            # 4. 淘汰逻辑：如果当前状态偏大
            # 只能让右指针向左移动，去寻找更小的值。
            right -= 1
            
    return 没有找到结果

---

3. 变形能力（大厂实战：三数之和 3Sum）

很多新手在做 Hot 100 的 LeetCode 15. 三数之和 时，能想到用双指针，但总是卡在“去重（去除重复解）”上，导致通过率惨不忍睹。这就是缺乏“变形能力”的体现。

题目大意： 给你一个包含 $n$ 个整数的数组 nums，判断 nums 中是否存在三个元素 $a, b, c$ ，使得 $a + b + c = 0$ ？请你找出所有和为 0 且不重复的三元组。

【思维突破与变形】

1. 无序变有序： 题目没说数组有序，但在求组合且不关心原索引的情况下，先排序是应用对撞指针的前提！排序后，相同的数字挨在一起，这为后续的“去重”打下了基础。
2. 降维打击： 三个数怎么找？我们先用一个 for 循环固定第一个数 nums[i]。那么剩下的任务，就是在 i 后面的区间里，寻找两个数，使得它们的和等于 -nums[i]。这就完美退化成了我们熟悉的模板！
3. 魔鬼细节（双重去重）： * 外层去重： 如果固定的 nums[i] 和上一个固定的数字一样，直接跳过，否则会产生重复的三元组。
   • 内层去重： 当 left 和 right 找到一组有效解后，在它们继续向中间夹逼时，必须跳过所有与当前值相等的重复元素。

【Python 3 满分代码 – 附带详细去重逻辑】

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # 必须先排序！时间复杂度 O(N log N)
        res = []
        n = len(nums)
        
        for i in range(n - 2):
            # 极端优化：如果排序后第一个固定的数都大于 0，后面的数肯定更大，三数之和绝对不可能等于 0，直接提前结束
            if nums[i] > 0:
                break
                
            # 外层去重：跳过重复的基准数 nums[i]
            if i > 0 and nums[i] == nums[i - 1]:
                continue
                
            # 转化为标准对撞指针模板
            left = i + 1
            right = n - 1
            target = -nums[i] # 我们需要 left 和 right 的和等于 target
            
            while left < right:
                current_sum = nums[left] + nums[right]
                
                if current_sum == target:
                    # 找到一组解
                    res.append([nums[i], nums[left], nums[right]])
                    
                    # 内层去重：跳过左指针后面的重复元素
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    # 内层去重：跳过右指针前面的重复元素
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                        
                    # 去重完成后，指针实质性地向内收缩一步，继续寻找下一组可能的解
                    left += 1
                    right -= 1
                    
                elif current_sum < target:
                    left += 1 # 和偏小，左指针右移放大
                else:
                    right -= 1 # 和偏大，右指针左移缩小
                    
        return res

时间复杂度分析： 排序 $O(N \log N)$ + 外层循环 $O(N)$ 嵌套内层双指针 $O(N)$，总体时间复杂度为 $O(N^2)$。这就是大厂面试官想看到的标准答案。

模板二：快慢指针 (Fast & Slow Pointers) —— 覆盖与清洗

1. 题型雷达（一秒识别快慢指针的专属战场）

当你看到以下三种信号，立刻将思维切换到快慢指针：

• 最强雷达一：“原地（In-place）修改”且“保持相对顺序”。 比如在数组中移除某些特定元素、删除有序数组的重复项。因为要保持顺序，不能随便交换，只能让快指针找到合法的元素，然后“抄写”到慢指针的位置。
• 最强雷达二：链表找环（Cycle）。 题目问链表有没有环、环的起点在哪里。这几乎是快慢指针（龟兔赛跑算法）的专属领域。
• 最强雷达三：链表寻找特定位置（中点、倒数第 K 个节点）。 面试官不允许你先遍历一遍求长度，再遍历一遍找位置。必须在一次遍历（One-pass）内完成。

---

2. 模板熟练度（数组与链表的双核驱动）

快慢指针在数组和链表中有两套截然不同、但必须烂熟于心的模板。

场景 A：数组的覆盖与清洗（如：删除有序数组中的重复项）

这里，快指针由 for 循环驱动，慢指针由条件触发。

Python

def remove_elements(nums):
    if not nums: return 0
    
    slow = 0 # 慢指针：指向当前最后一个确定保留的有效元素
    
    # 快指针：遍历所有元素，寻找需要保留的“合格品”
    for fast in range(1, len(nums)):
        if 满足保留条件(nums[fast], nums[slow]):
            # 找到合格品，慢指针前移一格，准备接收
            slow += 1
            # 将快指针找到的值，强行覆盖写入慢指针的位置
            nums[slow] = nums[fast]
            
    # 返回有效区域的长度（索引 + 1）
    return slow + 1 

场景 B：链表的“龟兔赛跑”（如：判断链表是否有环）

这里，快慢指针都由 while 循环驱动，但步长不同。通常慢指针走一步，快指针走两步。

Python

def has_cycle(head):
    # 初始化：两者都从起点出发
    slow = head
    fast = head
    
    # 只要快指针前面的路还没断，就继续跑
    while fast and fast.next:
        slow = slow.next       # 慢指针走一步（龟）
        fast = fast.next.next  # 快指针走两步（兔）
        
        # 核心逻辑：如果有环，跑得快的早晚会从后面套圈追上跑得慢的
        if slow == fast:
            return True # 发现环！
            
    return False # 跑到了尽头（遇到 None），说明没有环

---

3. 变形能力（大厂实战：Killer 级别的链表推导）

基础的去重和判断环，大家都背过模板。但在 Hot 100 中，有一道让无数新手在白板面试时折戟沉沙的魔鬼变种题：LeetCode 142. 环形链表 II。

题目大意： 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。不允许修改给定的链表。

【思维突破与变形】

这题的难点在于，快慢指针相遇时，相遇点大概率不是环的入口！怎么利用这个相遇点找到入口？这需要极其严密的数学推导，也是面试官最爱听的逻辑。

1. 第一阶段（找相遇点）： 按照模板 B，让龟（slow）和兔（fast）赛跑。如果没有相遇，直接返回 None。如果相遇了，记录下相遇节点。
2. 第二阶段（神级变形 – 找入口）：
   • 假设从头节点到环入口的距离是 $a$。
   • 从环入口到相遇点的距离是 $b$。
   • 从相遇点继续走到环入口的距离是 $c$（所以环的周长是 $b+c$）。
   • 相遇时，慢指针走了 $a+b$。快指针走了 $a+n(b+c)+b$（跑了 $n$ 圈）。
   • 因为快指针的速度是慢指针的 2 倍，所以时间相同，路程是 2 倍：$2(a+b) = a+n(b+c)+b$。
   • 化简这个公式：$a = c + (n-1)(b+c)$。
   • 终极结论： $a = c$（加上若干圈）。这意味着：如果此时让一个新指针从链表头部出发，让慢指针继续从相遇点出发，两人每次都只走一步。当他们相遇时，相遇的位置一定绝对是环的入口！

滑动窗口

1. 题型雷达（一秒锁定“窗口”区）

当你在读题时，只要看到以下信号的组合，请毫不犹豫地在大脑中画出一个“窗口”：

• 绝对雷达一：“连续”二字。 题目明确要求找“连续子数组（Subarray）”或“子串（Substring）”。只要出现“连续”且要求某种极值（最长、最短）或特定条件，90% 是滑动窗口。
• 绝对雷达二：寻找“最长”、“最短”或“正好满足条件”的区间。
• 隐藏前提（与前缀和的区别）：必须具备“单调性”。
  • 老师敲黑板： 我们在第一课讲过，如果数组里有负数，求和等于 $K$ 的连续子数组，必须用前缀和+哈希表。
  • 为什么？因为有负数时，窗口变大，和不一定变大（可能加了个负数反而变小了）。这就失去了“当条件不满足时，可以通过缩小窗口来寻找解”的单调性基础。只有当元素全为正数，或者条件本身具备单调性（比如：窗口内的不同字符数量）时，滑动窗口才能成立。

---

2. 模板熟练度（“进-算-出”的毛毛虫骨架）

滑动窗口的代码结构可以说是所有算法中最具有节奏感的。无论题目怎么变，它的骨架永远是“四步曲”：右指针进窗口 -> 更新状态 -> 判断左指针是否需要出窗口 -> 更新结果。

黄金模板：毛毛虫伸缩法

Python

def sliding_window(s: str):
    # 1. 初始化：左右指针和窗口内的状态记录器（通常是 dict, set 或一个计数变量）
    left = 0
    window_state = {} 
    res = 0 # 记录最终结果（最大长度、最小长度等）
    
    # 2. 右指针主动向右扩张（毛毛虫伸头）
    for right, char in enumerate(s):
        # 将新元素加入窗口状态
        window_state[char] = window_state.get(char, 0) + 1 
        
        # 3. 核心：判断当前窗口状态是否【破坏了规则】？
        # 如果破坏了，左指针必须被迫向右收缩（毛毛虫收尾），直到窗口重新合法
        while 窗口状态不满足题目要求:
            # 准备将左指针指向的元素移出窗口
            left_char = s[left]
            window_state[left_char] -= 1
            # 左指针实质性右移
            left += 1
            
        # 4. 更新结果：此时窗口一定是合法的！
        # 如果求最长：在 while 结束后更新
        res = max(res, right - left + 1) 
        
    return res

---

3. 变形能力（大厂实战：无重复字符的最长子串）

我们直接拿 Hot 100 里知名度最高、几乎是各大厂面试必考的 LeetCode 3. 无重复字符的最长子串 来实操。

题目大意： 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

• 输入: s = "abcabcbb"
• 输出: 3 (因为无重复字符的最长子串是 "abc"，所以其长度为 3)

【思维突破与变形】

1. 雷达触发： “最长” + “子串（连续）” + 判断是否有重复字符。完美契合滑动窗口。
2. 状态定义： 我们需要知道窗口里有没有重复字符。显然，用一个 set 来记录窗口内当前的字符是最合适的（利用它 $O(1)$ 的查找速度）。
3. 套用模板节奏：
   • right 指针一直向右走，把遇到的字符尝试往窗口里塞。
   • 如果 set 里已经有这个字符了（规则被破坏），说明出现了重复！
   • 此时 left 指针开始行动，把最左边的字符从 set 里踢出去，并向右移动，直到把那个引起重复的罪魁祸首踢出窗口为止。

子串

1. 题型概述：子串题目的“灵魂”

在面试中，“子串”或“子数组”的核心特征可以用两个字概括：连续。

无论是字符串中的字符，还是数组中的数字，只要题目强调“连续”这一属性，它就大概率落入我们的子串题型雷达中。（注意与“子序列 Subsequence”区分，子序列是可以不连续的，通常用动态规划解决）。

题目特征：

• 对象： 字符串或一维数组。
• 目标： 寻找满足特定条件的连续区间。
• 常见设问： 求“最长”、“最短”、“总个数”或“特定和”。

---

2. 识别题型快不快：面试场上的“秒懂”技巧

在紧张的面试中，你需要通过题目描述中的关键字瞬间锁定解法，不要陷入暴力的 $O(N^2)$ 陷阱。请把以下关键字刻在脑子里：

• 看到“连续” + “最长/最短” + “满足某条件” $\rightarrow$ 滑动窗口。
  • 潜台词： 窗口像毛毛虫一样向前爬，右边进，左边出。
• 看到“连续” + “和为 K” / “个数” $\rightarrow$ 前缀和 + 哈希表。
  • 潜台词： 尤其是数组里有负数时，滑动窗口会失效（因为右移不一定增大，左移不一定减小），必须上“前缀和”。
• 看到“连续” + “最大/最小的滑动区间” $\rightarrow$ 单调队列。
  • 潜台词： 窗口大小固定或在滑动，需要时刻知道窗口内的极值。

---

3. 题型雷达 + 模板熟练度 + 变形能力

Hot 100 中的子串题，雷达主要扫描到两个最核心的武器：滑动窗口和前缀和。

核心武器一：滑动窗口 (Sliding Window)

这是解决大部分子串极值问题的神兵利器。你需要把下面的模板练成肌肉记忆：

通用模板思路：

Python

def slidingWindow(s: str):
    # 1. 初始化维护变量（如：哈希表记录字符频率、当前窗口的和、最大/最小长度等）
    window = {}
    left = 0
    ans = 0 # 或 float('inf')
    
    # 2. 右指针主动扩张
    for right in range(len(s)):
        # 将 s[right] 加入窗口，更新维护的变量
        window[s[right]] = window.get(s[right], 0) + 1
        
        # 3. 判断当前窗口状态是否满足“收缩”条件（核心难点：何时收缩？）
        while (窗口不符合题目要求 / 或者寻找最短子串时窗口已符合要求):
            # 记录或更新答案（根据求最长还是最短，更新答案的位置可能在while内或外）
            
            # 准备收缩：将 s[left] 移出窗口，更新维护的变量
            window[s[left]] -= 1
            left += 1 # 左指针被动收缩
            
        # 4. 记录或更新答案（求最长子串时，通常在这里更新）
        ans = max(ans, right - left + 1)
        
    return ans

变形能力测试：

• 基础变形： “无重复字符的最长子串”（右侧无脑进，遇到重复就一直缩左边，直到把重复的踢出去）。
• 进阶变形： “最小覆盖子串”（找最短，所以是在 while 循环内部，即窗口满足条件时更新答案，然后尝试缩小窗口看能不能更短）。

核心武器二：前缀和 + 哈希表 (Prefix Sum + Hash Map)

当题目涉及求子数组的和，并且要求算出个数，或者数组中存在负数时，滑动窗口就废了，请立刻切到这个模板。

通用模板思路：

Python

def subarraySum(nums: List[int], k: int) -> int:
    # 1. 初始化哈希表，记录前缀和出现的次数。
    # 极其重要：必须初始化 {0: 1}，代表前缀和为0的情况出现了一次（即什么都不选的情况）
    prefix_map = {0: 1} 
    current_sum = 0
    count = 0
    
    # 2. 遍历数组，计算当前前缀和
    for num in nums:
        current_sum += num
        
        # 3. 核心逻辑：如果 current_sum - k 存在于哈希表中，说明找到了一段和为 k 的子数组
        if (current_sum - k) in prefix_map:
            count += prefix_map[current_sum - k]
            
        # 4. 把当前前缀和加入哈希表
        prefix_map[current_sum] = prefix_map.get(current_sum, 0) + 1
        
    return count

变形能力测试：

• 基础变形： “和为 K 的子数组”（直接套用上述模板）。
• 思维变形： 如果题目问的是“和能被 K 整除的子数组”，怎么办？（把哈希表里存的“前缀和”改成“前缀和对 K 的余数”即可）。

太棒了，非常有条理！单调队列（Monotonic Queue）往往是新手刚接触时觉得最“绕”、最容易写出 Bug 的结构之一。但在面试中，它是一个极具区分度的杀手锏。只要把它的底层逻辑想通，它其实就是滑动窗口的“进阶版插件”。

我们立刻开始拆解核心武器三：单调队列。

核心武器三：单调队列

1. 题型概述：单调队列的“灵魂”

如果说普通的滑动窗口关心的是“窗口里所有元素的总和或频次”，那么单调队列关心的就是“窗口里的霸主（最大值/最小值）”。

在单调队列中，有一句非常经典的算法名言来形容它的核心机制：

“如果一个选手比你年轻（在数组中靠后），还比你强（值比你大），那你就永远打不过他了，你可以直接退役了。”

题目特征：

• 对象： 一维数组。
• 动作： 存在一个大小固定或动态变化的滑动窗口。
• 目标： 频繁且快速（$O(1)$ 时间复杂度）地获取当前窗口内的最大值或最小值。

---

2. 识别题型快不快：单调队列的“雷达”

单调队列的雷达触发条件非常苛刻，一旦命中，几乎没有平替方案（用堆/优先队列的话，时间复杂度通常是 $O(N \log K)$，而单调队列是严格的 $O(N)$）。

• 看到“滑动窗口” + “求区间最大值 / 最小值” $\rightarrow$ 单调队列。
  • 潜台词： 窗口在动，进去一个新的，出来一个旧的，还要立刻知道现在的最大/最小是谁。
• 看到“连续子数组” + “最大值与最小值的差值 $\le limit$” $\rightarrow$ 双单调队列。
  • 潜台词： 既然要知道区间里的最大和最小，那就干脆维护两个队列，一个单调递减（管最大），一个单调递增（管最小）。

---

3. 模板熟练度：核心操作与代码框架

单调队列本质上是一个双端队列（Deque）。为了方便判断窗口是否越界，队列中通常存放的是元素的“索引（下标）”而不是“值”。

我们以 Hot 100 中最经典的求滑动窗口最大值为例，需要维护一个单调递减的队列：

通用模板思路：

Python

import collections

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    # 1. 初始化双端队列（存索引）和结果数组
    q = collections.deque()
    ans = []
    
    for i in range(len(nums)):
        # 2. 入队操作（维护单调性）：
        # 如果新来的元素比队列尾部的元素大，尾部元素“退役”（弹出）
        while q and nums[q[-1]] <= nums[i]:
            q.pop()
        q.append(i) # 新元素的索引入队
        
        # 3. 出队操作（维护窗口大小）：
        # 检查队头元素（最大值的索引）是否已经掉出了当前窗口 [i-k+1, i]
        if q[0] <= i - k:
            q.popleft()
            
        # 4. 记录答案：
        # 当窗口完全形成后（即索引 i 达到了 k-1），队头永远是当前窗口的最大值
        if i >= k - 1:
            ans.append(nums[q[0]])
            
    return ans

关键点死记硬背：

1. 右边进，踢掉弱者： 保证队列里的元素大小是单调的。
2. 左边出，踢掉老者： 保证队列里的元素都在合法窗口内。
3. 队头永远是答案： 要最大值，就维护单调递减；要最小值，就维护单调递增。

---

4. 变形能力测试

单调队列的变形往往不在队列本身，而在于“窗口何时滑动”。

• 基础题（定长窗口）： LeetCode 239. 滑动窗口最大值。窗口大小固定为 $k$，直接套用上述模板，左边界出队条件非常明确（q[0] <= i - k）。
• 进阶变形（变长窗口）： LeetCode 1438. 绝对差不超过限制的最长连续子数组。窗口大小不固定！右指针一直往右走，元素进入两个单调队列（一个维护最大，一个维护最小）。当 最大值 - 最小值 > limit 时，左指针开始向右收缩，同时将被踢出窗口的元素的索引从对应的单调队列头部移出。

普通数组

1. 题型概述：普通数组的“灵魂”

普通数组题目通常不再死盯着“连续”不放，而是利用数组天然的特性——索引（下标）和全排列/前后的整体关系来做文章。

题目特征：

• 对象： 一维数组或二维数组（如区间）。
• 限制： 经常会附带严苛的时间和空间复杂度要求，比如要求 $O(N)$ 时间和 $O(1)$ 额外空间。
• 目标： 重组、合并、找规律、或者利用数学性质计算。

---

2. 识别题型快不快：普通数组的“四大雷达”

在面试场上，看到数组题如果没有马上想到双指针或滑动窗口，请立刻启动以下四个雷达：

• 看到“多个区间 (Intervals)” + “合并 / 重叠 / 插入” $\rightarrow$ 排序 + 贪心合并。
  • 潜台词： 只要是区间题，90% 的第一步都是按左端点排序，然后看右端点能不能连贯起来。
• 看到“求某个位置的值，依赖于它左边所有元素和右边所有元素” $\rightarrow$ 前后缀分解（左右两趟遍历）。
  • 潜台词： 不要用两层 for 循环，先从左到右扫一遍，再从右到左扫一遍，信息就全了。
• 看到“找缺失的数字 / 找重复的数字” + 强调“时间 $O(N)$，空间 $O(1)$” $\rightarrow$ 原地哈希。
  • 潜台词： 不能开辟新数组？那就把输入数组本身当成哈希表来用，“让每个数字回到它应该在的下标位置上”。
• 看到“最大子数组和” $\rightarrow$ Kadane 算法（贪心/极简动态规划）。
  • 潜台词： 只要前面的累加和是负数，对现在就只有副作用，果断抛弃，从头开始算。

---

3. 题型雷达 + 模板熟练度 + 变形能力

Hot 100 中普通数组最核心、最具代表性的三个武器，你需要做到手写无 Bug：

核心武器一：区间合并 (Merge Intervals)

这是面试中极高频的一类题（如 LeetCode 56. 合并区间）。它的核心就是排序。

通用模板思路：

Python

def merge(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals: return []
    
    # 1. 极其关键：按照区间的左端点进行升序排序
    intervals.sort(key=lambda x: x[0])
    
    ans = [intervals[0]] # 先把第一个区间放进来作为“当前合并区间”
    
    # 2. 从第二个区间开始遍历
    for i in range(1, len(intervals)):
        curr_start, curr_end = intervals[i]
        last_merged_start, last_merged_end = ans[-1]
        
        # 3. 判断是否重叠：如果当前区间的左端点 <= 前一个区间的右端点
        if curr_start <= last_merged_end:
            # 发生重叠，更新前一个区间的右端点（取两者最大值）
            ans[-1][1] = max(last_merged_end, curr_end)
        else:
            # 不重叠，当前区间是一个新的起点，直接加入结果集
            ans.append(intervals[i])
            
    return ans

• 变形能力测试： “插入区间”（LeetCode 57）。给你一个已经合并好的区间列表和一个新区间，怎么插进去？（可以直接把新区间加进去，然后再套用上面的合并模板；更优的解法是模拟，分三段处理：在新区间左侧的、与新区间重叠的合并、在新区间右侧的）。

核心武器二：前后缀分解 (Prefix and Suffix Sweep)

专治“除了自己以外的整体运算”（如 LeetCode 238. 除自身以外数组的乘积）。

通用模板思路：

要求：不能用除法，时间 $O(N)$。

Python

def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [1] * n
    
    # 1. 第一趟遍历（从左到右）：计算每个元素左边所有元素的乘积
    left_product = 1
    for i in range(n):
        ans[i] = left_product # ans[i] 暂时只存左边的乘积
        left_product *= nums[i]
        
    # 2. 第二趟遍历（从右到左）：计算每个元素右边所有元素的乘积，并直接乘到 ans[i] 里
    right_product = 1
    for i in range(n - 1, -1, -1):
        ans[i] *= right_product # 左边乘积 * 右边乘积 = 最终结果
        right_product *= nums[i]
        
    return ans

• 变形能力测试： “接雨水”（LeetCode 42）。接雨水的最基础 $O(N)$ 解法就是前后缀分解。当前柱子能接多少水，取决于它左边最高的柱子和右边最高的柱子。分别用两个数组预处理出 left_max 和 right_max 即可。

核心武器三：原地哈希 (In-place Hashing)

这个技巧极其“流氓”，但它是解决 $O(1)$ 空间找缺失数字的唯一解法（如 LeetCode 41. 缺失的第一个正数）。

核心思想：一个萝卜一个坑。 数字 i 就应该被放在下标 i-1 的位置上。比如数字 1 放在下标 0，数字 2 放在下标 1。

通用模板思路：

Python

def firstMissingPositive(nums: List[int]) -> int:
    n = len(nums)
    
    # 1. 把所有萝卜放到属于它的坑里
    for i in range(n):
        # 如果当前数字属于 [1, n] 范围内，并且它没有待在正确的坑里
        # nums[i] 应该待在 nums[i] - 1 这个下标位置
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # 把它和它该去的坑里的萝卜交换！
            # 注意：Python 这里交换的写法有坑，必须先计算目标索引
            target_idx = nums[i] - 1
            nums[i], nums[target_idx] = nums[target_idx], nums[i]
            
    # 2. 遍历找茬：第一个不在正确坑里的萝卜，对应的就是缺失的最小正数
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
            
    # 如果 1 到 n 都在坑里了，那缺失的就是 n + 1
    return n + 1

矩阵

1. 题型概述：矩阵的“灵魂”

矩阵本质上是一个二维数组 $M \times N$。它的灵魂在于坐标 (row, col) 以及特定的移动方向。

题目特征：

• 对象： $M \times N$ 的网格。
• 操作： 遍历、旋转、标记、搜索。
• 难点： 1. $O(1)$ 空间限制： 许多题目要求原地修改，不能开辟新的 $M \times N$ 空间。2. 边界控制： 上下左右四个边界的精准锁定。3. 坐标映射： 旋转或翻转后，老坐标 $(r, c)$ 如何变到新坐标 $(r’, c’)$。

---

2. 识别题型快不快：矩阵的“雷达”

面试时，看到矩阵题，请迅速在脑海中连线以下雷达点：

• 看到“螺旋 (Spiral)”遍历 / 填充 $\rightarrow$ 四边界收缩模拟。
  • 潜台词： 不要试图写一个复杂的 if-else 来控制方向，直接定义上下左右四个边界，走完一行/一列，边界就往里推一步。
• 看到“原地 (In-place) 修改” + 标记某些行/列 $\rightarrow$ 利用首行/首列作为标记位。
  • 潜台词： 不能开辟新哈希表记下哪些行要变 0？那就借用矩阵自己的第一行和第一列来记录。
• 看到“行和列分别有序” + 搜索目标值 $\rightarrow$ “对角线（起点）缩小法”。
  • 潜台词： 这不是普通的二分查找，而是利用行/列的单调性，从特定顶点（比如右上角）开始，要么划掉一行，要么划掉一列。
• 看到“图像旋转” $\rightarrow$ （我们在普通数组提过的）多次翻转法。

---

3. 题型雷达 + 模板熟练度 + 变形能力

我们需要练就这三个肌肉记忆模板：

核心武器一：四边界收缩模拟 (Spiral Traversal Template)

专治 LeetCode 54. 螺旋矩阵。核心是维护 top, bottom, left, right 四个变量。

通用模板思路：

Python

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]: return []
    m, n = len(matrix), len(matrix[0])
    ans = []
    
    # 1. 初始化四个边界
    t, b, l, r = 0, m - 1, 0, n - 1
    
    # 2. 循环遍历，直到边界交叠
    while True:
        # a. 从左到右（在 top 行）
        for i in range(l, r + 1): ans.append(matrix[t][i])
        t += 1 # top 边界下移
        if t > b: break # 检查是否结束
        
        # b. 从上到下（在 right 列）
        for i in range(t, b + 1): ans.append(matrix[i][r])
        r -= 1 # right 边界左移
        if l > r: break
        
        # c. 从右到左（在 bottom 行）
        for i in range(r, l - 1, -1): ans.append(matrix[b][i])
        b -= 1 # bottom 边界上移
        if t > b: break
        
        # d. 从下到上（在 left 列）
        for i in range(b, t - 1, -1): ans.append(matrix[i][l])
        l += 1 # left 边界右移
        if l > r: break
        
    return ans

• 熟练度关键： range 的左闭右开区间，以及每一个 for 循环后立刻进行的边界更新和 break 检查。

核心武器二：借用首行首列做标记 (In-place Marking Template)

专治 LeetCode 73. 矩阵置零。要求空间 $O(1)$。

通用模板思路：

1. 先用两个 boolean 变量记录： 第一行和第一列原本是否存在 0。
2. 遍历剩余部分（从 1,1 开始）： 如果 matrix[i][j] == 0，则将第一行和第一列对应的位置标记为 0：matrix[0][j] = 0, matrix[i][0] = 0。
3. 再次遍历剩余部分（根据标记置零）： 如果首行或首列对应位置是 0，则该点置零。
4. 最后处理： 根据第一步的 boolean 变量，决定是否把第一行和第一列整体置零。

核心武器三：有序矩阵搜索（Top-Right Start Template）

专治 LeetCode 240. 搜索二维矩阵 II。

如果从 $(0,0)$ 开始，往右是变大，往下也是变大，无法做出唯一决策。但如果从右上角 (0, n-1) 开始：

• 当前值 > target： target 只可能在当前值的左边，col--（划掉当前列）。
• 当前值 < target： target 只可能在当前值的下边，row++（划掉当前行）。
• 这是一个 $O(M+N)$ 的极优算法。

链表

1. 题型概述：链表的“灵魂”

如果说数组的灵魂是“下标定位”，那么链表的灵魂就是“牵一发而动全身的指针”。

链表在内存中是不连续的，你只有一条线索（head）。一旦你在修改指针时不小心把线索剪断了，后面的数据就永远丢失了。

题目特征：

• 对象： 单向链表、双向链表（Hot 100 绝大部分是单向）。
• 痛点： 1. 无法通过下标 $O(1)$ 访问，必须老老实实从头遍历。2. 如果要删除或修改头节点（Head），逻辑往往和修改普通节点不一样。3. 遍历时极易越界（访问了 None.next）。

---

2. 识别题型快不快：链表的“四大雷达”

在面试场上，链表题的套路非常固化，看到以下关键字，直接拔出对应的武器：

• 看到“合并” / “删除” / “头节点可能会变化” $\rightarrow$ 虚拟头节点（Dummy Node）。
  • 潜台词： 凡是结果可能换个新头的题，第一行代码无脑写 dummy = ListNode(-1); dummy.next = head，这能帮你省去 80% 的边界条件判断（if head is None:）。
• 看到“找中点” / “判断环” / “倒数第 $K$ 个节点” $\rightarrow$ 快慢指针（双指针）。
  • 潜台词： 链表不能回头，也不能提前知道长度。要想只遍历一次就找到特定位置，只能让两个人以不同的速度或者固定的间距一起跑。
• 看到“反转” / “K 个一组翻转” $\rightarrow$ 三指针反转法（迭代）。
  • 潜台词： 这是字节跳动等大厂最爱考的硬核基本功，没有取巧的办法，必须做到闭着眼睛也能写出核心循环。
• 看到“两个链表找交点” $\rightarrow$ 浪漫双指针（走过你来时的路）。
  • 潜台词： 链表 A 走完了去走 B，链表 B 走完了去走 A。因为 $A+B = B+A$，如果有交点，他们一定会相遇。

---

3. 题型雷达 + 模板熟练度 + 变形能力

链表题的核心考察点就是“穿针引线”。以下三大核心武器，请务必刻在骨子里。

核心武器一：基础中的基础——反转链表 (Reverse Linked List)

无论是“反转部分链表”、“回文链表”还是“K 个一组反转”，底层全都是这个模板。

通用模板思路（极其重要：pre, cur, nxt 三步曲）：

Python

def reverseList(head: ListNode) -> ListNode:
    pre = None
    cur = head
    
    while cur:
        nxt = cur.next      # 1. 极其关键：修改当前指针前，先把下一步的节点存下来，防止断链！
        cur.next = pre      # 2. 穿针引线：把当前节点指向前面
        pre = cur           # 3. 前指针前移
        cur = nxt           # 4. 当前指针前移
        
    return pre              # 循环结束时 cur 为空，pre 刚好停在原来链表的尾部（新链表的头部）

• 熟练度测试： 面试官常问：“空间复杂度是多少？” 答：“迭代法是 $O(1)$，如果用递归法是 $O(N)$，因为有隐式的系统调用栈开销。”（大厂面试通常要求你写迭代法）。

核心武器二：万能护城河——虚拟头节点 (Dummy Node)

这其实不是一个算法，而是一个极其优雅的工程技巧（例如 LeetCode 21. 合并两个有序链表）。

通用模板思路：

Python

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    # 1. 创建虚拟头节点，它的值不重要
    dummy = ListNode(-1)
    # 2. 用一个游标指针 cur 来负责“穿针引线”
    cur = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next # 游标向前移动
        
    # 3. 谁还没走完，就把剩下的整串直接挂到 cur 后面
    cur.next = l1 if l1 else l2
    
    # 4. 真正的新链表头部是 dummy.next
    return dummy.next

核心武器三：时空刺客——快慢指针 (Fast & Slow Pointers)

专治不知道链表长度的尴尬情况（例如 LeetCode 141. 环形链表 / 876. 链表的中间结点）。

通用模板思路（找中点为例）：

Python

def middleNode(head: ListNode) -> ListNode:
    slow = head
    fast = head
    
    # 极其关键的循环条件：fast 必须保证自己和自己的下一步不是空，才能走两步
    while fast and fast.next:
        slow = slow.next          # 慢指针走一步
        fast = fast.next.next     # 快指针走两步
        
    # 当 fast 走到尽头，slow 刚好在正中间
    return slow

• 变形能力测试： * 环形链表： 如果 fast 和 slow 相遇了，说明有环。
  • 环形链表 II（找入环点）： 当快慢相遇后，把其中一个指针重新移回 head，两人同时每次走一步，再次相遇的地方就是环的起点。（这是一个纯数学推导，面试时直接当结论用即可）。
  • 删除倒数第 N 个节点： 让 fast 先走 N 步，然后 fast 和 slow 一起走，fast 到底时，slow 刚好停在倒数第 N+1 个节点上（方便执行删除操作）。