Hot 100 全解：按知识点串讲

要完成的任务

给定整数数组 nums 和整数 target，找出两个不同位置，使这两个位置上的数之和等于 target，返回它们的下标。答案中的两个下标可按任意顺序排列。

字段与保证

nums[i] 是下标 i 处的整数；同一个数组元素不能重复使用。题目保证每组输入恰好存在一个有效答案。

全部示例

约束与进阶

• 2 ≤ nums.length ≤ 104。
• -109 ≤ nums[i], target ≤ 109。
• 只存在一个有效答案；进阶要求设计时间复杂度低于 O(n²) 的算法。

暴力起手：双层循环枚举所有下标对 (i, j)，判 nums[i] + nums[j] == target，O(n²)。慢的根源：外层每固定一个数，内层都要重新把数组扫一遍去找它的另一半——前面扫过的元素明明都"见过"，却没留下任何可直接查询的记录，同一批元素被一遍遍重扫。

① 关键转化——把"枚举数对"换成"枚举单数 + 查另一半"：当前值 value 一固定，另一半根本不用枚举——它被等式唯一确定为 complement = target - value。于是每轮真正的问题只剩一个：complement 这个值之前出现过吗？在哪个下标？这正是字典「值 → 下标」的 O(1) 拿手活，n² 次数对验证退化成 n 次 O(1) 查询。这套「存我见过的、查我需要的」模式，也是 LC560 查「前缀和 − k」的底层零件。

② 只查左边为什么不漏：常见困惑——seen 只装当前位置左侧的元素，万一我的另一半在右边呢？不漏：设答案是 (i, j) 且 i < j，扫到 j 时 i 必然已写入 seen。每一对都在它靠后的那个成员处被发现，恰好一次——所以每个数只需对"左边"负责，单向一趟就覆盖全部数对。

③ 三个量的身份：

④ "先查后存"从身份表直接推出：seen 的身份是"左侧世界"，那么第 index 轮查询时它就不能含 value 自己——写入必须放在查询之后。这一个顺序同时解决了"同一元素不能用两次"：当 target = 2 × value 时，查 complement 只可能命中左边的同值元素，绝不会命中自己；反过来"先存后查"就是把自己也放进了候选。

⑤ 用样例验证关键一步：[3,3], target=6：i=0 查 complement=3，seen 还是空表 → 未命中，写入 {3:0}；i=1 再查 complement=3 → 命中下标 0，返回 [0,1]。两个 3 来自不同下标，顺序对了就天然不自配。多解法取舍：若数组已排序可用对撞双指针省掉 O(n) 空间，但本题输入未排序且要原下标，哈希一趟最直接（细节见段5追问）。

里程碑①  主例开始：nums=[2,7,11,15]，target=9，seen={}
里程碑②  i=0,value=2：complement=7 未命中；本轮结束 seen={2:0}
里程碑③  i=1,value=7：complement=2 命中历史下标 0；返回 [0,1]
里程碑④  重复值例 [3,3]：第一个 3 先查空表，再写 seen={3:0}
里程碑⑤  第二个 3 查询时尚未写入自身，只会命中下标 0，不会得到 [1,1]

class Solution:
    def twoSum(self, nums, target):
        # 1. seen 只保存当前位置之前的“值 → 下标”
        seen = {}

        # 2. 每轮先查补数，未命中再记录当前值
        for index, value in enumerate(nums):
            complement = target - value
            if complement in seen:
                return [seen[complement], index]
            seen[value] = index
        return []

时间 O(n)，每个元素做一次补数查询并至多写入哈希一次；空间 O(n)，最坏存下几乎所有元素——用 O(n) 空间换掉暴力 O(n²) 里被重复扫描的时间。高频追问一："数组已排序还用哈希吗？"——排序数组可对撞双指针，O(n) 时间、O(1) 额外空间；但本题要返回原下标，若自己排序就得先绑定 (值, 原下标) 再排，O(n) 空间并没省下来，未排序输入直接哈希一趟最划算。追问二："哈希查询一定是 O(1) 吗？"——是均摊/期望 O(1)，极端冲突下单次会退化，面试口径答"均摊 O(1)"；要最坏保证可换平衡树，查询 O(log n)。

功能：[2,7,11,15],9 → [0,1]；边界：最短两元素 [3,3],6 → [0,1]（重复值也要能命中）；特殊：含负数 [-1,-2,-3],-5 → [1,2]、目标依赖后面元素 [3,2,4],6 → [1,2]（先查后存保证不选到自身）。

考点：哈希表把"查找另一半"降到 O(1)，"先查后存"的顺序细节。通用范式收束：找"两个元素凑成某条件"→ 单层枚举 + 哈希记录历史、查询所需搭档——存我见过的，查我需要的。识别信号：题面要"两个数满足某等式"、要求返回位置或原始下标、输入未排序——先想「值 → 下标」哈希，再考虑排序双指针。关联：↔ LC15 三数之和（固定一个数后退化为两数之和）、↔ LC560 和为K的子数组（同款"查需要的另一半 = 前缀和 − k"）。

要完成的任务

给定字符串数组 strs，把互为字母异位词的字符串放进同一组并返回所有分组。字母异位词由完全相同的字符及次数组成，只是排列顺序可以不同；分组顺序和组内顺序均不作要求。

全部示例

约束

• 1 ≤ strs.length ≤ 104。
• 0 ≤ strs[i].length ≤ 100，因此空字符串是合法输入。
• strs[i] 只包含小写英文字母。

暴力起手：逐对判断"这两个词是否互为异位词"（各自排序后判等），把判定同组的合并，O(n²·k log k)（n 个词、词长 k）。n ≤ 10⁴ 时约 5×10⁷ 个词对、每对还要排序比较，必然超时。慢的根源："属于哪一组"每次都靠两两比较现场重算——eat、tea、ate 同组这件事被反复验证，却始终没有一个能直接查的组标识。

① 关键转化——把"两两比较"换成"各自算指纹"：异位词的定义＝字符及各自次数完全相同，只有排列顺序不同。顺序是唯一的自由度，那就把它抹掉：对词内字符排序，''.join(sorted(word))——eat、tea、ate 排序后都是 aet。于是"互为异位词"⇔"规范形相等"，组籍判断从两两比较变成一次字典查询，问题退化成标准子问题：按 key 分桶。这与 LC1 同款——哈希 O(1) 命中，只是 key 从"值本身"升级成"自己设计的规范形"。

② 第二种指纹——把定义直接写成数据：等价条件既然是"26 个字母的次数都相同"，也可跳过排序，统计出长度 26 的 counts，转成 tuple(counts) 当 key。取舍：排序法每词 O(k log k)、代码短；计数法每词 O(k)，但前提是字符集已知且固定（这里是小写字母），任意 Unicode 输入时排序法更通用。

③ 谁当 key、谁进桶（本题最容易存错的一步）：

④ key 为什么必须拼成 str / 转成 tuple：字典 key 要求可哈希（不可变），而 sorted(word) 返回 list、计数数组 counts 也是 list，直接当 key 会抛 TypeError。所以排序法必须 ''.join(...)、计数法必须 tuple(...)——这不是代码风格，是能不能运行的问题。

⑤ 常见困惑——指纹会不会"撞车"把不同组错并？不会。排序串和 26 位计数元组都是"字符及次数"的无损表示：从指纹能唯一还原每个字母各几个，因此指纹相等 ⇔ 字符及次数相同 ⇔ 互为异位词。至于字典内部的哈希冲突，Python 会用键判等自动化解，不影响分组正确性。

⑥ 用样例验证：["eat","tea","tan"]：eat→aet 新建桶；tea→aet 命中同桶；tan→ant，与 aet 不同，另开新桶——同组必聚、异组必分。空串 "" 也有稳定指纹（"" / 全 0 元组），无需特判。

strs=["eat","tea","tan","ate","nat","bat"]
里程碑①  groups={}
里程碑②  eat→aet，tea→aet：{aet:[eat,tea]}
里程碑③  tan→ant：{aet:[eat,tea], ant:[tan]}
里程碑④  ate→aet，nat→ant：{aet:[eat,tea,ate], ant:[tan,nat]}
里程碑⑤  bat→abt：形成第三桶；返回三个桶的列表

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs):
        # 1. 相同排序指纹共享同一个桶
        groups = defaultdict(list)
        for word in strs:
            signature = ''.join(sorted(word))
            groups[signature].append(word)
        return list(groups.values())

from collections import defaultdict

# 计数元组变体：字符集固定为 26 个小写字母
class Solution:
    def groupAnagrams(self, strs):
        groups = defaultdict(list)
        for word in strs:
            # 1. 为当前单词构造不可变的计数指纹
            counts = [0] * 26
            for character in word:
                counts[ord(character) - ord('a')] += 1

            # 2. list 不可哈希，转 tuple 后再归组
            signature = tuple(counts)
            groups[signature].append(word)
        return list(groups.values())

时间 O(n·k log k)，n 个词、每个排序 k log k（k 为词长）；计数元组做 key 可降到 O(n·k)。空间 O(n·k)，所有词都要存进桶。高频追问一："排序法和计数法怎么选？"——k ≤ 100 时两者都远快于两两比较，排序法代码短更稳；字符集固定且 k 大时计数法有渐进优势；字符集不固定（任意 Unicode）时 26 位计数元组失效，退回排序法或改用 (字符, 次数) 有序元组。追问二："真正被卡掉的是什么？"——是 O(n²·k) 的两两比较：n=10⁴ 时约 5×10⁷ 对；指纹法把"跟谁同组"变成 O(1) 查桶，总量只有 10⁶ 级。

功能：上例 6 词分 3 组；边界：含空串 [""] → [[""]]、单词 ["a"] → [["a"]]；特殊：全部互为异位词 ["abc","bca","cab"] → 一组、无任何异位词全是独立组。

考点：为哈希 key 设计规范化指纹（排序 / 字符计数），以及"指纹当 key、原词进桶"的角色分离。通用范式收束：按等价关系分组 → 为每个等价类构造唯一规范形，一趟哈希分桶，替代 O(n²) 两两比较。识别信号：题面出现"互为…词 / 本质相同只是顺序（或表示）不同 / 把相同的归为一组"→ 先问"这类对象的规范形是什么"。关联：↔ LC438 找所有字母异位词（同样靠"字符计数相等"判定异位词，但在滑动窗口里动态维护）、↔ LC1 两数之和（同为"用哈希把匹配 O(1) 化"的思路）。

要完成的任务

给定未排序整数数组 nums，返回其中最长“连续整数序列”的长度。这里的连续指数值依次相差 1，元素不要求在原数组中相邻；目标算法需达到 O(n) 时间。

全部示例

约束

• 0 ≤ nums.length ≤ 105，空数组答案为 0。
• -109 ≤ nums[i] ≤ 109。
• 数组可以包含重复值，且输入没有预先排序。

暴力起手：直觉一：排序后线性扫，相邻差 1 加长、相等跳过、断开重置，O(n log n)。直觉二：对每个数 x 用哈希集合向右数 x+1, x+2, …——但 [1,2,…,n] 这种整段输入下，段里每个成员都会把自己右边重数一遍，总步数 n + (n−1) + … ＝ O(n²)。慢的根源：同一段连续序列被它内部的每个成员重复清点。

① 约束排除法：题目点名要 O(n)，这一刀先杀掉排序路线（O(n log n) 绕不开）。剩下的只有"不排序也能 O(1) 回答某数在不在"→ 哈希集合 set(nums)。而直觉二离正解只差一步：别让段里每个成员都清点，给每段指定唯一的清点负责人。

② 关键转化——只从段的最左端起数：一段连续序列 [a, a+1, …, b] 里，只有最左端 a 满足"a-1 不在集合"；其余成员都有前驱。于是把枚举对象从"每个数"换成"每段的最左端"：只有通过 value - 1 not in values 检查的值才向右清点，整段恰好被数一次。这与 LC84"每个矩形只记在最矮柱账上"是同一招——给每个答案单元指定唯一负责人，天然不重不漏。

③ 各个量的身份（length 一身二职）：

④ 判据方向从直觉推导：识别一段只需认出它的一个端点。"无前驱（value-1 不在）＋向右数"，或"无后继（value+1 不在）＋向左数"，都对；错的是混搭——右端判据配向右数，每段只能数出 1（见坑①）。习惯取"无前驱 + 向右"，与从小数到大的直觉一致。

⑤ 常见困惑——for 里套 while，凭什么还是 O(n)？while 只有段最左端能进入，清点的又恰是自己段内的成员：每个元素一生只被"它所在段的最左端"探测一次，所有 while 的总步数＝各段长之和 ≤ n。这是摊还分析——内层预算全局共享，不能按"每轮最坏 × 轮数"相乘。另一个困惑——"不加起点判据答案也对，为什么必须加？"对，结果不会错，但退化成直觉二的 O(n²)，10⁵ 规模直接超时：起点判据不是正确性开关，是复杂度开关。

⑥ 用样例验证：[100,4,200,1,3,2] → values={1,2,3,4,100,200}。候选起点只有 100（99 不在）、200（199 不在）、1（0 不在）；从 1 起探测 2、3、4 连续命中，5 缺席，length 定格 4，longest=4。而 4 因为前驱 3 在集合被一票淘汰——省下的正是"段内成员重复清点"那份冤枉工。

nums=[100,4,200,1,3,2] → values={1,2,3,4,100,200}
里程碑①  100 的前驱 99 不在集合：起点，序列 [100]，longest=1
里程碑②  4 的前驱 3 在集合：不是起点，跳过
里程碑③  200 的前驱 199 不在集合：序列 [200]，longest 仍为 1
里程碑④  1 是起点，连续命中 2、3、4，遇 5 停止
里程碑⑤  本段长度 4，更新 longest=4；2、3 后续均因有前驱而跳过

class Solution:
    def longestConsecutive(self, nums):
        # 1. 去重，并支持均摊 O(1) 的成员查询
        values = set(nums)
        longest = 0

        # 2. 只有没有前驱的值才启动一次完整扩展
        for value in values:
            if value - 1 in values:
                continue

            length = 1
            while value + length in values:
                length += 1
            longest = max(longest, length)
        return longest

时间 O(n)：内层 while 的总步数＝各段长之和 ≤ n——摊还分析，双层循环不能按"每轮最坏 × 轮数"相乘，非起点会被 continue 挡掉。空间 O(n) 存 set。高频追问一："最坏会退化吗？"——算法本身的步数严格 O(n)，唯一的不确定来自哈希：set 查询是均摊/期望 O(1)，对抗性哈希冲突下单次会退化，面试口径答"均摊 O(n)"。追问二："能不能 O(1) 空间？"——不能同时保住 O(n) 时间：不给额外空间就只剩排序路线（原地排序 O(n log n) / O(1)），时间与空间在本题是二选一的取舍。

功能：[100,4,200,1,3,2] → 4；边界：空数组 [] → 0、单元素 [5] → 1；特殊：含重复 [1,2,2,3] → 3（set 去重）、含负数与断层 [0,-1,1] → 3。

考点：用 set 换 O(1) 归属查询，"只从起点清点"的摊还分析。通用范式收束：答案由互不重叠的段组成时，为每段指定唯一负责人（最左端），只在负责人处结算整段——不重不漏，总工作量与元素数同阶。识别信号：求"最长连续 / 成段结构"、输入无序、题面点名 O(n) 且排序超标 → set + "无前驱才起数"。关联：↔ LC1 两数之和（同为哈希 O(1) 查询）、↔ LC560 和为K的子数组（都是"用哈希把 O(n²) 优化到 O(n)"的经典范例）、↔ LC84 柱状图最大矩形（同款"唯一负责人结算"的不重不漏思想）。

要完成的任务

给定整数数组 nums，把所有 0 移到数组末尾，同时保持所有非零元素原有的相对顺序。必须直接修改输入数组，不能复制出另一份完整数组；返回值为 None，力扣展示的是修改后的 nums。

全部示例

约束与进阶

• 1 ≤ nums.length ≤ 104。
• -231 ≤ nums[i] ≤ 231-1。
• 需要原地完成，并尽量减少写入或交换次数。

暴力起手：新开一个数组，按序抄入全部非零数、尾部补 0，再整体拷回原数组——O(n) 时间但 O(n) 空间。另一条直觉是"遇到 0 就删掉、往末尾 append"：Python 的 list.pop(index) 每次要整体左移后面的元素，是 O(n)，最坏退化 O(n²)。慢和费的共同根源：没有意识到每个非零数的最终位置其实当场就能确定。

① 约束排除法＋关键转化：题目画了两支箭头。"原地"杀掉抄数组做法；"保持非零数相对顺序"杀掉"遇 0 就和末尾交换"这类不稳定分区（会把靠后的非零数提到前面）。两条路堵死后只剩一条：0 的最终位置取决于非零数有多少、不好直接定，但第 k 个非零数的最终位置就是下标 k-1，完全确定——于是视角从"把 0 往后挪"换成"把非零数往前搬"，一趟扫描逐个搬到位。

② 读写双指针与三个区间的身份：fast 负责读、slow 负责指定写入位置，数组被它们切成三段：

③ 为什么一次 swap 就够——从"0 区"直接推出：fast 读到非零数时，若 slow < fast，中间 [slow, fast) 全是 0，故 nums[slow] 必是 0：交换＝把非零数填进空位、同时把一个 0 丢到 fast 处——一步办完两件事，不需要"扫完再补 0"的第二趟。若前缀还没出现过 0，则 slow == fast，交换是自己换自己的 no-op；这不是浪费，而是让三区不变量在"有 0 / 无 0"两种局面下统一成立，省掉特判。

④ 保序与末尾全 0 都是不变量的推论：非零数被 fast 读到的先后＝它们在原数组的先后，而落点 slow 单调递增，先读到的落得更靠前，相对顺序自然不变；扫完后 [0, slow) 装下了全部非零数，[slow, n) 只剩被换出去的 0。

常见困惑——交换会不会把某个还没读到的非零数甩到后面、造成二次搬运把顺序弄乱？不会：被换到 fast 位置的永远是 nums[slow]，它要么是 0（slow < fast 时），要么就是 fast 自己（slow == fast 时）——非零数从不向后移动，每个非零数至多被搬一次。

⑤ 用样例验证一步：[0,1,0,3,12] 走到 fast=3（读到 3）时 slow=1，此刻数组为 [1,0,0,3,12]，中间 [1,3) 恰好是两个 0——正是"0 区"。交换位置 1、3 得 [1,3,0,0,12]：非零区扩成 [0,2)，一个 0 被丢到位置 3，三区不变量继续成立。

样例：[0, 1, 0, 3, 12]      slow = 下一个非零待填位

① 遇到 0：跳过          [0, 1, 0, 3, 12]   slow=0
② 遇到 1：与位置0交换   [1, 0, 0, 3, 12]   slow=1
③ 遇到 3：与位置1交换   [1, 3, 0, 0, 12]   slow=2
④ 遇到12：与位置2交换   [1, 3, 12, 0, 0]   slow=3（完成）

扫完后 [0,3)=[1,3,12] 是保序非零，[3,5)=[0,0] 自然是 0。注意第 1、3 步 slow 停着不动，让 0 攒在 slow 位等着被后面的非零换走。

class Solution:
    def moveZeroes(self, nums):
        # 1. slow 指向下一个非零数应该放入的位置
        slow = 0

        # 2. fast 按原顺序读取；只有读到非零数才写入并推进 slow
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1

时间 O(n)，单趟扫描；空间 O(1)，原地交换、无额外数组。交换写法天然稳定（保序）。高频追问一："swap 版和'覆盖+补零'版哪个写入更少？"覆盖版固定写 n 格（非零数写前段 + 0 补尾）；swap 版只在 slow < fast 时真正动数据，写入 = 2 × "第一个 0 之后的非零数个数"——0 少或靠后时 swap 几乎不写，但 0 在最前、后面全非零时（如 [0,1,1,…,1]）swap 要写约 2n 格反而更多，两者按数据分布取舍。追问二："为什么不遍历时 pop 掉 0 再 append 到尾部？"list.pop(index) 是 O(n)，最坏 O(n²)；而且边遍历边删会让下标跳过元素，正确性都难保证。

功能：[0,1,0,3,12] → [1,3,12,0,0]；边界：空 []、单元素 [0] / [1]；特殊：无零 [1,2,3] 不变、全零 [0,0,0]、零在开头/结尾。

考读写双指针的三区不变量与保序性。通用范式收束：原地筛选且要求保持相对顺序 → 读写双指针——fast 按原序读、slow 收成品前缀，不变量是"[0, slow) 已完工"。识别信号：题面同时出现"原地 / 不复制数组"与"保持相对顺序 / 把某类元素移到一端"。关联：↔ LC11 盛最多水的容器（同为双指针但是对撞型：本题两指针同向各司读写，11 题两指针相向夹逼淘汰）、↔ LC15 三数之和（命中后跳过重复值用的也是同向推进）。

要完成的任务

给定长度为 n 的整数数组 height。第 i 条竖线连接坐标 (i,0) 与 (i,height[i])。选择两条线与 x 轴组成容器，返回能容纳的最大水量；容器不能倾斜。

两线下标为 left、right 时，宽度为 right-left，有效高度由较短线决定，因此面积为 min(height[left],height[right])×(right-left)。

全部示例

约束

• n == height.length，2 ≤ n ≤ 105。
• 0 ≤ height[i] ≤ 104。

暴力起手：枚举所有线对 (i, j)，算 min(height[i], height[j]) × (j-i) 取最大，O(n²)；n ≤ 10⁵ 时约 5×10⁹ 次计算，必然超时。慢的根源：绝大多数组合"生死早已注定"——某条线一旦注定当矮壁、宽度又只会更窄，它参与的一整批组合都不可能翻盘，但暴力仍然逐个去算，这种"可整批排除"的信息完全没被利用。

① 关键转化——从"逐对枚举"换成"从最宽开始、每步整批淘汰"：把还没验证过的组合看成候选区间 [left, right]：从两端（宽度最大）出发，每结算一对，就证明"某条线剩下的全部组合都不如刚结算的这一对"，然后让这条线永久退场。每步淘汰一条线，n 步恰好覆盖全部约 n²/2 个组合——这就是对撞指针。它是本类的母题：LC15 的内层、LC42 的双指针版都是同一套"夹逼淘汰"。

② 每个量的身份：注意两个指针各有双重身份，"不漏解"的证明全靠第二重：

③ 为什么移矮壁——从"宽度只减"这条直觉推：指针只能向内走，宽度必然变小，想让面积变大，唯一的希望是高度变大。而高度 = 两壁较矮者：留着矮壁，高度天花板就钉死在它头上——对面换得再高，min 也超不过矮壁，"宽减、高不增"，面积只会缩水。所以只有换掉矮壁，高度才可能抬升。这一步还只是"值得试"，下一步证明它一个都不漏。

常见困惑——移走矮壁 left 后，"以 left 为左壁、右壁在中间"的那些组合从没算过，凭什么不漏？设 height[left] ≤ height[right]，任取中间一条线 k（left < k < right）：组合 (left, k) 的面积 = min(height[left], height[k]) × (k-left)，其中高度项 ≤ height[left]（min 被矮壁封顶，k 多高都没用），宽度项 < right-left——两项都不占优，面积必然 ≤ 刚结算的 (left, right)。也就是说刚才那一次结算，已经替 left 把它全部剩余组合的最大可能"预支"了，left 可以安心退场。每一步都带着这个证明淘汰一条线，所以这不是碰运气的贪心，而是逐步整批排除的完整枚举。

④ 顺序与等高：其一，先结算面积、再移指针——循环第一轮结算的正是全场最宽的组合，先移后算会直接跳过它。其二，两壁等高时双方同为矮壁，上面的排除论证对两侧同时成立，移哪边都不漏；代码归入 else 统一移 right，无需特判。

⑤ 用样例验证第一步的"整批淘汰"：[1,8,6,2,5,4,8,3,7]：left=0（高 1）、right=8（高 7），结算 1×8=8。此举淘汰的是 (0,k)，k=1..7 共 7 个组合：每个面积 ≤ 1×7=7 < 8——矮壁 1 封死高度、宽度又更窄，确实一个都翻不了盘。下一轮 left=1（高 8）立即结算出 7×7=49，即最终答案。

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

① left=0(1), right=8(7)：面积 1×8=8   → 左边矮，left 右移
② left=1(8), right=8(7)：面积 7×7=49  → 更新答案 49，right 左移
③ left=1(8), right=6(8)：面积 8×5=40  → 仍小于 49
④ 后续宽度继续缩小，最大值不再改变

结论：最大容器由下标 1 和 8 围成，答案 49。

注意第 1 步后 left 一直停在 idx1（值 8，全场最高）没再动过——因为之后每一步都是右侧更矮，始终在移 right。移高侧只会更小，正是"移短板"贪心的体现。

class Solution:
    def maxArea(self, height):
        # 1. 从宽度最大的两端开始
        left, right = 0, len(height) - 1
        best_area = 0

        while left < right:
            # 2. 结算当前容器，并保留目前最大面积
            width = right - left
            current_area = min(height[left], height[right]) * width
            best_area = max(best_area, current_area)

            # 3. 宽度必然缩小，所以只移动限制高度的短板
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return best_area

时间 O(n)，两指针共走 n 步；空间 O(1)。高频追问一："这是贪心，怎么证明不漏解？"标准回答：每移一次矮壁＝淘汰"以它为一端的全部剩余组合"，这些组合高被矮壁封顶、宽更窄，都 ≤ 刚结算的值（见段2 的排除论证），n 步恰好淘汰完全部组合——本质是每步带证明的整批排除，不是启发式。追问二："要求返回最优的两条线下标怎么改？"在 best_area 更新的同一分支里同步记录 (left, right) 即可，复杂度不变。

功能：[1,8,6,2,5,4,8,3,7] → 49；边界：两条线 [1,1] → 1；特殊：递增 [1,2,3,4] → 4、全等高 [5,5,5] → 10、含 0。

考对撞指针与"移矮壁"的排除式证明。通用范式收束：答案由一对端点决定、收缩时一个维度（宽度）单调变差 → 对撞指针，每步以"矮壁封顶"为由整批淘汰一端。识别信号：求"两个下标的最优组合"、目标形如 min(两端量)×距离、数组可从两端夹逼。关联：↔ LC42 接雨水（同为对撞 + 矮侧先定论：11 题矮壁定面积上限，42 题矮侧定水位）、↔ LC15 三数之和（内层就是同款有序对撞收缩）。

要完成的任务

给定整数数组 nums，找出所有三元组 [nums[i],nums[j],nums[k]]，要求三个下标两两不同且三个数之和为 0。返回结果中不能出现重复三元组；三元组内部顺序与结果整体顺序均不作要求。

全部示例

约束

• 3 ≤ nums.length ≤ 3000。
• -105 ≤ nums[i] ≤ 105。
• 输入可以含重复值，但输出按三元组的值去重。

暴力起手：三重循环枚举 (i, j, k) 判和为 0，O(n³)；n ≤ 3000 时约 4.5×10⁹ 次，超时。慢的根源有两个：其一，固定前两个数后，第三个数只能是 -nums[i]-nums[j] 这一个值，却还在整个数组里盲找；其二，重复值会把同一个"值三元组"生成很多遍，最后还得靠集合兜底去重。

① 约束排除法——"不含重复三元组"指向排序：去重难在相同值散落各处、全局比对代价大。排序让重复值相邻，"跳过重复"退化成"和前一个比一下"；同时数组有序后，"和太小往右换大的、太大往左换小的"才有方向可言。一次排序同时解决去重与查找两个难题——这就是正解第一行是 nums.sort() 的原因。

② 关键转化——固定一个数，三降二：枚举三元组中最小的那个数 nums[index]（排序保证它排最前），剩下的任务变成：在右侧有序区间 [index+1, n-1] 里找两个数使和为 -nums[index]。这正是 LC1 两数之和的有序版——有序版不必用哈希，直接套 LC11 同款对撞收缩。

③ 三个下标的身份：

④ 内层对撞为什么不漏——LC11 的排除逻辑原样搬来：current_sum < 0 时，nums[left] 换更靠左的搭档只会更小，它已无翻身可能，永久出局（left 右移）；> 0 时对称淘汰 nums[right]。每步至少淘汰一个候选，内层一轮 O(n) 扫完该区间全部两数组合。

⑤ 三道去重哨卡——位置与方向都从"排序后重复相邻"推出：
其一 外层与前一个比：index > 0 and nums[index] == nums[index-1] 才跳过，保证每个值只当一次固定数。
其二 命中后跳 left：收集完再 while nums[left] == nums[left-1]: left += 1，跳过会拼出同样三元组的左端。
其三 命中后跳 right：对称地 while nums[right] == nums[right+1]: right -= 1。

常见困惑——外层跳过重复的 index，会不会把 [-1,-1,2] 这种自身就含重复值的答案漏掉？不会。哨卡跳的是"同一个值第二次当固定数"：第一个 −1 当固定数时，它的搜索区间里还留着第二个 −1，[-1,-1,2] 在那一轮就已收集；轮到第二个 −1 再跑一遍，只会把同样的组合重收一次。"和前一个比"恰好保证：每个值当固定数有且只有一次，而且是搜索区间最大的那一次。

⑥ 用样例验证：[-1,0,1,2,-1,-4] 排序得 [-4,-1,-1,0,1,2]。index=1（第一个 −1）：left=2（−1）、right=5（2），和为 0 → 收 [-1,-1,2]；内缩后 left=3（0）、right=4（1），和又为 0 → 收 [-1,0,1]。index=2（第二个 −1）与前一个相同被整轮跳过——重复的 [-1,-1,2] 正是在这一岗被拦下。

排序后：[-4, -1, -1, 0, 1, 2]

① 固定 -4：右侧最大两数和为 1+2=3，连同 -4 仍只有 -1，整轮无解
② 固定 -1：left=-1，right=2  → 和为 0，收集 [-1,-1,2]
③ 继续内缩：left=0，right=1 → 和为 0，收集 [-1,0,1]
④ 下一个 -1 与前一个固定数重复，整轮跳过
⑤ 固定 0：最小组合 0+1+2>0，无解

答案：[[-1,-1,2], [-1,0,1]]

index=0 那轮 left 一路右移始终凑不够（固定数太小），空手而归；index=2 因为和 index=1 同为 −1 被去重整轮跳过——正是这一步避免了重复的 [-1,-1,2]。

class Solution:
    def threeSum(self, nums):
        # 1. 排序后，双指针才具有可控的增减方向
        nums.sort()
        triplets = []

        # 2. 固定第一个数，把问题降为右侧区间的两数之和
        for index in range(len(nums) - 2):
            if nums[index] > 0:
                break
            if index > 0 and nums[index] == nums[index - 1]:
                continue

            left, right = index + 1, len(nums) - 1
            while left < right:
                current_sum = nums[index] + nums[left] + nums[right]

                # 3. 利用有序性调整当前和
                if current_sum < 0:
                    left += 1
                elif current_sum > 0:
                    right -= 1
                else:
                    triplets.append([nums[index], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # 4. 命中后跳过相同端点，避免重复三元组
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return triplets

时间 O(n²)：排序 O(n log n) + 外层 n × 内层双指针 O(n)。空间 不计输出时，Python list.sort()（Timsort）最坏需要 O(n) 辅助空间；双指针扫描本身只用 O(1)。高频追问一："不排序、用哈希行不行？"行但不划算：内层用哈希找 -a-b 同样是 O(n²)，可"按值去重"必须把每个三元组规范化（组内排序）后塞集合，代码更绕、常数更大；排序的 O(n log n) 被 O(n²) 吸收，不亏。追问二："内层命中后又移指针又跳重复，会不会超 O(n)？"不会——left 只增、right 只减，跳重复消耗的也是同一份移动预算，每轮内层总移动不超过区间长度。

功能：[-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]（组内与组间顺序按本实现排序后输出）；边界：不足 3 个元素返回 []；特殊：全零 [0,0,0,0] → [[0,0,0]]（考去重）、无解 [1,2,3] → []、多重复值。

考排序预处理、固定一数降元、有序对撞与三处去重的配合。通用范式收束：k 数之和 → 排序 + 固定 k−2 个数 + 最内层有序对撞；"结果按值去重" → 排序让重复相邻，在固定位与命中两端三处跳过。识别信号：找"和为定值"的组合、结果要求不含重复组合、允许改变元素顺序。关联：↔ LC1 两数之和（内层就是它的有序版，对比哈希 vs 双指针）、↔ LC11 盛最多水的容器（同款对撞收缩的排除证明）、↔ LC42 接雨水（同族对撞指针）。

要完成的任务

给定 n 个非负整数 height，每个数表示宽度为 1 的柱子高度。下雨后，水会停在柱子之间且不能高于左右挡板；返回整张高度图能够接住的雨水总量。

全部示例

约束

• n == height.length，1 ≤ n ≤ 2×104。
• 0 ≤ height[i] ≤ 105。

一句话总纲：先把总水量拆成一列一列的账——每列接水量 = min(左侧最高, 右侧最高) − 自身柱高；再从两端向中间对撞，每轮把较矮一端的那一列当场结算并向内走一步；两指针相遇时所有列都已结算，累计值就是答案。

① 核心洞察——一列的水位由两侧最高柱中较矮的那根决定：整片水洼形状不规则，直接算无从下手，先只盯住某一列，问"它头顶能停多高的水"。水要停得住，左边必须有柱子挡着——水位最多齐平左侧最高柱，再高就从左边溢走；右边同理。所以这一列的水位 = min(左侧最高柱, 右侧最高柱)，减去自身柱高就是本列水量，全题答案 = 逐列水量之和。（暴力做法就是对每列向左右各扫一遍找这两个"最高"，O(n²)；慢的根源是"左侧最高"在相邻两列之间只差一根柱子，却每列都从头重扫，信息毫无复用。）

② 先修一版可提交的解——按列预计算（段4 解法二）："每列答案 = 左侧统计量与右侧统计量取 min"，这正是 LC238 除自身以外数组的乘积的套路：答案需要两侧信息，就各扫一趟、把每个方向"目前为止的最高"存进数组。left_max[index] 记下标 0..index（含自身）里的最高柱高，从左往右一趟递推；right_max[index] 对称地从右往左。这两条数组连起来看，就是罩在柱子上方、从两侧只升不降的"包络"轮廓线（段3、段4 沿用这个叫法）。最后逐列累加 min(left_max[index], right_max[index]) − height[index]。O(n) 时间、O(n) 空间，已是可提交的正解；代价是两条辅助数组。

③ 再省掉两条数组——对撞双指针（段4 解法一，主解）：结算一列真正用到的只是那个 min：只要能确定哪一侧是短板，另一侧的精确值根本不重要。于是学 LC11 盛最多水的容器从两端向中间走：比较两端柱高，较矮的一端，它这一列的水位已经被"自家这侧的最高"钉死——因为对面正立着一根比它更高的柱子兜底，min 一定落在自家这侧。矮侧当场结算、向内走一步，两条包络数组就退化成 left_max、right_max 两个标量，空间 O(1)。（另有一条"横着按层结算"的单调栈路线：遇到右壁时弹栈、一层一层加水，与 LC84 柱状图中最大的矩形互为镜像；同为 O(n) 但要维护栈，面试首选上面两法，此处不展开。）

④ 每个量的身份：

⑤ 循环体的顺序从"水量不能为负"推出：结算一列必须先 left_max = max(left_max, height[left])，后累加 left_max − height[left]。当前列若刷新了最高，先更新再相减恰好得 0——它自己就是新挡板，头顶无水；反过来先减后更会算出负数，把总量倒扣（坑②的反例）。

判据也别混：这套代码里每轮比较的是两端柱高 height[left] 与 height[right]，不是 left_max 与 right_max——两套判据各配一套写法，混搭会漏结算（坑①的反例）。

⑥ 常见困惑——right_max 只看过 [right..n-1]，中间一大段还没扫，凭什么能替左列担保"右侧够高"？因为结算左列用的不是右侧的精确最高，而是一个下界：height[right] 本人就站在左列右边，而能进左分支的前提正是 height[left] < height[right]——右侧"至少这么高"，min 必然落在左侧手里，左列水位就是 left_max。

再追一层："万一 left_max 比右侧真实最高还高，min 取错边怎么办？"这种局面根本进不了左分支：左侧真有超高柱时，height[left] < height[right] 一直不成立，左指针被那根超高柱卡住不动，改由右指针带着自己确切的 right_max 一路结算过来。用 [5,1,3] 验证：left 全程卡在高 5 的柱上，凹槽（高 1）由右分支以 right_max=3 结算得 3−1=2，与真值 min(5,3)−1=2 一致。

⑦ 用原题示例走一遍：height=[0,1,0,2,1,0,1,3,2,1,2,1]，初始 left=0、right=11，left_max=right_max=0，总量 0。

left=0（高 0）< right=11（高 1）：结算左端，left_max→0，水 0，left→1。
left=1（高 1）不小于 right=11（高 1）：结算右端，right_max→1，水 0，right→10。
left=1（高 1）< right=10（高 2）：结算左列，left_max→1，水 0，left→2。
left=2（高 0）< right=10（高 2）：left_max=1 不变，接 1−0=1 格，累计 1，left→3。
接着右侧连续结算：right=10（高 2）把 right_max 推到 2、水 0；right=9（高 1）接 2−1=1 格，累计 2；right=8（高 2）水 0，right→7。
此后 left=3..6（高 2,1,0,1）都小于 right=7（高 3）：left_max 先被下标 3 推到 2，下标 4、5、6 依次接 1、2、1 格，累计 6。
left 与 right 在下标 7（全场最高柱）相遇，循环结束，输出 6，与示例一致。

缩小例：[1, 0, 2, 0, 1]      答案 = 2

① 两端同高，先结算右端：水量 0，right→3
② 位置3高度0，右侧最高1：接 1 格水，累计 1
③ 左端高度1小于中间高度2：结算左端 0 格
④ 位置1高度0，左侧最高1：接 1 格水，累计 2
⑤ 指针在高度2处相遇；中间柱贡献必为0，无需单独结算

最终柱高+水位：[1,1,2,1,1]（下标1、3两个凹槽各补 1 格）

缩小例最终 total_water=2；上方原例按同样步骤得到 6。每轮严格按“更新 max → 累加 total_water → 移动一侧指针”的代码顺序执行。

缩小例两法答案都是 2（原例都是 6）。对撞双指针省掉两条包络数组，只保留 left_max/right_max 两个标量。

class Solution:
    def trap(self, height):
        # 1. 从两端向中间走，并记录两侧已经见过的最高柱
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        total_water = 0

        while left < right:
            # 2. 较矮一侧的封顶已经确定，可以立即结算该位置
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                total_water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                total_water += right_max - height[right]
                right -= 1

        return total_water

# 解法二：前缀数组，O(n) 时间、O(n) 空间
class Solution:
    def trap(self, height):
        if not height:
            return 0

        # 1. 分别预处理每个位置两侧（含自身）的最高柱
        length = len(height)
        left_max = [0] * length
        right_max = [0] * length
        left_max[0] = height[0]
        for index in range(1, length):
            left_max[index] = max(left_max[index - 1], height[index])

        right_max[-1] = height[-1]
        for index in range(length - 2, -1, -1):
            right_max[index] = max(right_max[index + 1], height[index])

        # 2. 每格水位由左右包络中较低的一条决定
        total_water = 0
        for index in range(length):
            total_water += min(left_max[index], right_max[index]) - height[index]

        return total_water

解法① 双指针：时间 O(n)，空间 O(1)；当 height[left]<height[right] 时右侧存在更高柱封顶，可安全结算左侧。解法② 前缀数组：时间 O(n)，空间 O(n)，额外保存 left_max/right_max 两条包络。高频追问一："while left < right 相遇的那一列没被结算，漏水了吗？"没有——每次移动的都是较矮一侧，谁也跨不过全场最高柱，两指针必在某根全场最高柱处相遇；该列水位 min(两侧最高) ≤ 自身柱高，水量为 0。追问二："面试怎么展示优化层次？"逐列公式 O(n²) → 两趟包络 O(n)/O(n)（LC238 套路）→ 发现只需分辨短板侧、压成 O(1) 对撞——能讲全三层正是本题作为 Hard 的考察点。

功能：[0,1,0,2,1,0,1,3,2,1,2,1] → 6；边界：空 / 少于 3 根 [2,0] → 0；特殊：单调递增或递减接不到水 [1,2,3] → 0、平台 [3,0,0,3] → 6。

考"逐列拆账 + 两侧包络"的分解与"短板侧可先结算"的空间压缩。通用范式收束：每个位置的答案 = min/max(左侧统计量, 右侧统计量) → 两个方向各预扫一趟再拼合；若只需分辨哪侧是短板，可进一步压成对撞双指针 O(1) 空间。识别信号：水位 / 容量 / 边界由"两侧极值中较小者"决定、总量可逐位独立累加。关联：↔ LC11 盛最多水的容器（同为对撞 + 矮侧定论：11 题算一对壁的面积，42 题逐列积水）、↔ LC84 柱状图中最大的矩形（互为镜像：一个找两侧最高来蓄水，一个被两侧第一根更矮限高）、↔ LC239 滑动窗口最大值（另一类"维护区间极值"，对比单调队列）。

要完成的任务

给定字符串 s，返回其中不含重复字符的最长子串长度。子串必须由原字符串中连续的一段字符组成，不能跳过字符拼成子序列。

全部示例

约束

• 0 ≤ s.length ≤ 5×104，空字符串答案为 0。
• s 可由英文字母、数字、符号和空格组成，并非只含小写字母。

暴力起手：枚举全部 (i, j) 子串再逐字符查重，O(n³)；改成对每个左端点用集合边右扩边查，也要 O(n²)。慢的根源：左端点每右移一格，右侧那段刚验证过"无重复"的字符被整段重扫——相邻两次枚举本可共享的查重结论完全没有被复用。

① 关键转化——换枚举对象：不枚举 O(n²) 个子串，改成对每个右端点 right 只问一件事：以 right 结尾的无重复子串，左端最远能伸到哪？把这个最远左端记作 left，每轮用 right-left+1 更新答案。任何最长子串总得结尾在某个 right 上，所以 n 个右端点就覆盖了全部候选。剩下的唯一问题：right 前进后，left 怎么快速跟进。

② left 只进不退、且不漏解（滑窗 O(n) 的正确性核心）：设上一轮 [left, right-1] 已是无重复窗口。right 前进后若出现重复，祸首只能是新字符 s[right]——旧的部分本来就互不相同，修复只需右移左端、把它的旧副本排出去。而 left 绝不需要回退：假如某个更靠左的 l < left 能与新 right 组成无重复窗口，那它的子串 [l, right-1] 也无重复，说明上一轮 left 根本不该停在这么靠右的位置，矛盾。所以"最远合法左端"随 right 单调右移，两个指针全程只前进——每个字符进窗口恰一次、出窗口至多一次，总动作 ≤ 2n。

③ 新 left 一步定位——记每个字符的最近下标：重复只可能由 s[right] 自己造成，所以只需知道它上一次出现在哪。用哈希表 last[c] 存字符 c 最近出现的下标：若旧副本还在窗口里（last[c] >= left），left 直接跳到 last[c]+1。这是 LC1 两数之和 的哈希套路换了个键值：那里存"值→下标"查补数，这里存"字符→最近下标"查旧副本。取舍：set 逐格缩版（发现重复后 while 逐个移出左侧字符）逻辑最直观，同为摊还 O(n)；dict 下标跳版一步到位、没有内层循环，本文采用后者。

④ 各量身份（last[c] 同一个量、两种时刻两种身份）：

⑤ 循环体三行的顺序从身份表直接推出：固定为"缩左 → 刷新 last[c]=right → 更新 best"。
先缩左再刷新：缩左要读的是旧副本的位置；若先写 last[c]=right，读到的就是自己（right >= left 恒成立），left 被挤到 right+1，窗口永远为空。
best 放最后：right-left+1 统计的必须是合法窗口，缩左之前窗口可能还带着重复。
刷新无条件执行：无论本轮有没有触发缩左，c 的最近位置都已变成 right；漏更新会留下过期下标，下次误判"旧副本不在窗口内"。

常见困惑——left 直接跳到 last[c]+1，被跳过的那些左端点不会漏掉答案吗？不会。任何满足 left ≤ l ≤ last[c] 的窗口 [l, right] 都同时框住下标 last[c] 和 right 这两个相同字符，全部注定非法；而以这些 l 开头、结尾更早的窗口，在之前的 right 轮次里已经统计过。被跳过的只有"必然非法"的组合，一个合法候选都没丢。

⑥ 用样例验证最险的一步："abba" 走到 right=3 读 a：此时 left=2（上一轮被重复 b 挤过来的），而 last[a]=0 < 2——旧 a 早已在窗口外，left 不动，窗口 "ba" 合法，best 保持 2。这一步正是判据必须带 last[c] >= left 的原因。

s = "a b b a"      下标 0 1 2 3      初始 left=0, last={}, best=0

r=0 后: [a]          last={a:0},             best=1
r=1 后: [a b]        last={a:0,b:1},         best=2
r=2 读到 b（旧 b=1 仍在窗口）:
  执行 left=2 后: a b [b] a     只移动左边界，last 仍是 {a:0,b:1}
  执行 last[b]=2 后:             last={a:0,b:2}，窗口仍为 "b"
r=3 读到 a（旧 a=0 已在窗口左侧）:
  不执行 left 赋值；执行 last[a]=3 后，窗口为 [b a]，best 仍为 2

class Solution:
    def lengthOfLongestSubstring(self, s):
        # 1. last 记录字符最近位置；[left, right] 始终保持无重复
        last = {}
        left = 0
        best = 0

        # 2. 右扩窗口；只有旧位置仍在窗口内时才移动 left
        for right, char in enumerate(s):
            if char in last and last[char] >= left:
                left = last[char] + 1

            # 3. 记录最新位置，再用当前合法窗口更新答案
            last[char] = right
            best = max(best, right - left + 1)

        return best

时间 O(n)：dict 下标跳版没有内层循环，每轮严格 O(1)；set 逐格缩版有内层 while，但也不退化——left 只前进、全程最多走 n 步，每个字符进窗口恰一次、出窗口至多一次，总动作 ≤ 2n。这是摊还分析：while 的弹出预算全局共享只有 n 个，不能按"每轮最坏 × 轮数"相乘成 O(n²)。空间 O(min(n, Σ))，Σ 为字符集大小，last 至多存 Σ 个键。高频追问一："全相同 "aaaa" 这种极端输入会退化吗？"不会：每轮 left 恰好跟着 right 走一步，窗口恒为 1，总移动仍是 2n。高频追问二："空间能不能 O(1)？"字符集固定（ASCII/小写字母）时 Σ 就是常数，本身已是 O(1)；字符集无界时必须记住"窗口里有哪些字符"，哈希表规模省不掉。

功能："abcabcbb" → 3、"pwwkew" → 3；边界：空串 "" → 0、单字符 "a" → 1；特殊：全相同 "bbbb" → 1、全不同 "abcdef" → 6、含空格/符号。

考点：变长滑窗维护"无重复"不变式、哈希记最近下标让 left 一步跳。收束——通用范式：求最长合法连续段、且合法性只会被新入元素破坏、收缩左端必能修复时，用变长滑窗：对每个右端点维护最远合法左端，left 只进不退，每元素进出窗口各至多一次即得 O(n)。识别信号：题面出现"最长连续子串/子数组"＋一个随窗口收缩只会变好的条件（无重复、至多 k 种字符、和不超过目标等）。关联：↔ LC438 找所有字母异位词（定长滑窗，对比变长）、↔ LC76 最小覆盖子串（反向：求"最短合法"，扩右修复、缩左试探）。

要完成的任务

给定两个字符串 s 和 p，找出 s 中所有长度等于 p.length、且与 p 互为字母异位词的连续子串，返回这些子串的起始下标。答案顺序不作要求。

字母异位词必须拥有完全相同的字符种类与出现次数，只允许排列顺序不同；不同匹配子串可以互相重叠。

全部示例

约束

• 1 ≤ s.length, p.length ≤ 3×104。
• s 与 p 只包含小写英文字母。
• 当 p.length > s.length 时不存在合法窗口，应返回空列表。

一句话总纲：先把 p 的字符频次数成一张目标计数表；再让一个长度固定为 len(p) 的窗口在 s 上从左到右逐格平移，每平移一步只更新"右端进一个、左端出一个"两个字符的计数；每当窗口计数与目标计数完全相同，就把窗口左端下标记入答案。

① 核心洞察一——异位词就是频次表相等：字母异位词只许打乱顺序、不许增删字符，所以两串互为异位词 ⇔ 26 个小写字母的出现次数逐一相同。顺序信息可以整个扔掉，比较对象从"子串"降维成一张计数表。这正是 LC49 字母异位词分组 的判据——那里给静态字符串分组，这里要把同一判据装到会移动的窗口上。

② 核心洞察二——窗口定长，平移一步只换两个字符：合法子串的长度被 p 锁死，记 window_size=len(p)、n=len(s)。起点相邻的两个窗口共享 window_size−1 个字符，真正不同的只有两个：右端新进来的 s[right]，和左端刚离开的 s[right-window_size]。所以计数表不必推倒重建，每步只改这两个键，更新是 O(1)。这也是本题与 LC3 无重复最长子串 的区别：那里窗口变长，要靠"条件被破坏"触发缩左；这里左右两端步调一致，只平移、不判缩。起点 0..n−window_size 逐个被检查、每个恰好一次，匹配可重叠也不怕漏。（暴力对每个起点截取子串排序再比较是 O(n·window_size·log window_size)，改成每段重数一遍频次也要 O(n·window_size)——慢就慢在把共享的 window_size−1 个字符的统计推倒重算，完全没用上"只有一进一出"这条关系。）

③ 解法①就此成型——每平移一步整表比较：先建好目标计数 need 和第一个窗口 s[0..window_size-1] 的计数 window；此后每轮右进一个、左出一个，计数减到 0 的键要删掉（否则和 need 判等会失败），再问一句 window == need，相等就记录左端。每轮判等最多比 26 个字母，成本 O(26)。

④ 记哪个下标、何时开始判，从"右减左加一"推出：窗口是闭区间 [left..right]，长度 right-left+1=window_size，解出 left=right-window_size+1——命中时写进答案的是这个左端，不是 right。第一个完整窗口出现在 right=window_size-1（下标从 0 起，刚好凑满 window_size 个字符），所以判满条件是 right >= window_size-1，多写或少写 1 都会错过或错位一个窗口。

⑤ 用原题示例走一遍（解法①）：s="cbaebabacd", p="abc"，need={a:1,b:1,c:1}，window_size=3。

初始窗口 [0..2]="cba"：window={c:1,b:1,a:1}，与 need 相等 → 命中，记左端 0。
right=3 进 e、出 c：窗口 "bae"，多了 e、缺 c，不等。
right=4 进 b、出 b：窗口 "aeb"，e 还在，不等。
right=5 进 a、出 a：窗口 "eba"，仍不等。
right=6 进 b、出 e：窗口 "bab"，{b:2,a:1}，b 超、缺 c，不等。
right=7 进 a、出 b：窗口 "aba"，{a:2,b:1}，不等。
right=8 进 c、出 a：窗口 "bac"，{b:1,a:1,c:1}，与 need 相等 → 命中，记 8−3+1=6。
right=9 进 d、出 b：窗口 "acd"，不等。结果 [0,6]。

⑥ 再省一步——用"达标种类数"免去整表比较（解法②）：解法①每轮都把 26 个字母问一遍，可其实每轮只有进、出两个字符的计数动了，其余字母的达标状态不可能变。于是引入两个计数器：required＝need 中计数为正的字符种类总数（固定不变）；matches＝此刻计数恰好等于需求（window[c]==need[c] 且 need[c]>0）的字符种类数。命中判定简化成一句 matches==required，每轮只在进、出两个字符处各做一次修正。

⑦ 各量身份（一张固定不动、一张随窗口动，别混用）：

⑧ matches 只在计数跨过 need[c] 的瞬间变化：matches 数的是"恰好相等"的种类数，所以只有计数跨越 need[c] 这条线的那一步需要修正，其余增减（远未达标、早已超标）都与它无关。以更新后的 window[c] 为判据：
右进 c（计数 +1）后：若 window[c]==need[c]，刚达标，matches+1；若 window[c]==need[c]+1，由达标转超标，matches−1。
左出 c（计数 −1）后：若 window[c]==need[c]，从超标落回达标，matches+1；若 window[c]==need[c]-1，跌破需求，matches−1。
四条对称成两对；need[c]==0 的字符整个跳过这套逻辑。

⑨ 用小例验证最容易错的一步——先进后出的"临时超长态"：s="abab", p="ab"，看 right=2 这一轮。

右进 a 后：window={a:2,b:1}，窗口临时含 3 个字符，a 超标，matches 由 2 降到 1。
左出 s[0]=a 后：window={a:1,b:1}，a 落回达标，matches 回到 2。
此刻才判定：命中，记起点 2-2+1=1。
超长的中间状态是真实存在的，命中判定必须放在左出完成之后，否则这一窗会被误判为"未达标"。

取舍：解法①每轮整表比较 window == need，成本 O(26)、几乎不会写错，小写字母场景首选；解法②用 matches 把每轮判定降到 O(1)，字符集很大（如 Unicode）时优势明显，代价是⑧里的四个临界时刻容易写错一个。

常见困惑——matches==required 只考核了 p 里有的字符，窗口里混进 p 没有的字符怎么办？混不进来。窗口长度恒为 window_size；全部需求字符恰好达标时，它们合计已占 sum(need)=window_size 个位置，恰好填满窗口，没有空位留给多余字符。反过来，只要有一个多余字符占位，必有某个需求字符缺一个，matches 立刻小于 required。封死漏洞的是"长度锁定"＋"全部恰好达标"两个条件的合力，单独哪个都不够。

s = "a b a b"     p = "a b"     window_size=2     need={a:1,b:1}

初始: [a b] a b       window={a1,b1}           → result=[0]
right=2 先右进 a: [a b a] b   window={a2,b1}   （暂时 3 个字符）
        再左出 a:  a [b a] b   window={a1,b1}   → result=[0,1]
right=3 先右进 b:  a [b a b]  window={a1,b2}
        再左出 b:  a b [a b]  window={a1,b1}    → result=[0,1,2]

注意：右进和左出之间的“超长临时窗口”是真实中间态，不能直接画成平移后的最终窗口。

from collections import Counter

class Solution:
    def findAnagrams(self, s, p):
        # 1. 窗口长度固定为 p 的长度；主串过短时直接结束
        window_size = len(p)
        if len(s) < window_size:
            return []

        # 2. 建立目标计数与第一个定长窗口
        need = Counter(p)
        window = Counter(s[:window_size])
        result = [0] if window == need else []

        # 3. 每轮右进一个字符、左出一个字符，窗口大小保持不变
        for right in range(window_size, len(s)):
            enter_char = s[right]
            leave_char = s[right - window_size]
            window[enter_char] += 1
            window[leave_char] -= 1

            # 减到 0 就删零键：手写 dict 判等时零键致败；Counter 仅 3.10+ 才忽略零计数
            if window[leave_char] == 0:
                del window[leave_char]

            # 4. 频次完全相同，记录当前窗口的左端点
            if window == need:
                result.append(right - window_size + 1)

        return result

# 解法二：用 matches 记录“频次恰好达标”的字符种类数
class Solution:
    def findAnagrams(self, s, p):
        # 1. 初始化目标频次和固定窗口状态
        window_size = len(p)
        if len(s) < window_size:
            return []

        need = [0] * 26
        window = [0] * 26
        for char in p:
            need[ord(char) - ord('a')] += 1

        required = sum(1 for count in need if count > 0)
        matches = 0
        result = []

        # 2. 右侧字符进入；只在计数跨过目标值时修正 matches
        for right, char in enumerate(s):
            enter_index = ord(char) - ord('a')
            window[enter_index] += 1
            if need[enter_index] > 0:
                if window[enter_index] == need[enter_index]:
                    matches += 1
                elif window[enter_index] == need[enter_index] + 1:
                    matches -= 1

            # 3. 窗口超长时移出左侧字符，并修正它的达标状态
            if right >= window_size:
                leave_char = s[right - window_size]
                leave_index = ord(leave_char) - ord('a')
                window[leave_index] -= 1
                if need[leave_index] > 0:
                    if window[leave_index] == need[leave_index]:
                        matches += 1
                    elif window[leave_index] == need[leave_index] - 1:
                        matches -= 1

            # 4. 窗口已满且所有目标字符都达标，记录左端点
            if right >= window_size - 1 and matches == required:
                result.append(right - window_size + 1)

        return result

时间 O(n)：每个字符右进窗口恰一次、左出至多一次——定长滑窗是"每元素进出各 ≤1 次"最规整的情形，连摊还论证都不需要。解法①每轮多一次 Counter 整表判等，严格说是 O(26·n)，字符集固定视为常数；解法②靠 matches 把每轮判定压到 O(1)。空间 O(1)：至多 26 个计数键。高频追问一："零计数键能不能不删？"手写 dict 不行（{a:0,b:1} 与 {b:1} 判等失败）；Counter 3.10+ 判等忽略零计数所以能过，但依赖版本行为、跨语言不可迁移，删零键才是通解。高频追问二："字符集扩到 Unicode 还是 O(n) 吗？"解法①每轮判等涨到 O(|Σ|)、总 O(n·|Σ|)；解法②的 matches 只做进出两个字符的临界检查，与 |Σ| 无关，仍是 O(n)——这正是解法②存在的意义。

功能：s="cbaebabacd",p="abc" → [0,6]、s="abab",p="ab" → [0,1,2]；边界：len(s)<len(p) 返回 []；特殊：p 全相同 p="aa"、s 中无匹配、s 与 p 等长。

考点：定长滑窗的增量平移、异位词＝频次表相等、matches 达标计数器。收束——通用范式：要在所有定长连续段上判定一个统计量时，让窗口平移、每步只增量修正进出两个元素的贡献；判据可整表比较，也可用"达标计数器"把每轮判定 O(1) 化。识别信号：题面出现"所有长度恰为 m 的子串/子数组"＋按频次/和/种类判定（找异位词、定长最大平均值、含指定字符集的定长段）。关联：↔ LC49 字母异位词分组（同款"计数相等"判据，静态分组版）、↔ LC3 无重复最长子串（变长 vs 定长：缩左的触发条件不同）、↔ LC76 最小覆盖子串（把"恰好等于"放宽成"覆盖 ≥"，窗口就从定长变成可伸缩）。

要完成的任务

给定整数数组 nums 和整数 k，统计和恰好等于 k 的非空连续子数组数量并返回。不同起止下标算不同子数组，即使它们包含的值相同。

数组元素允许为负数、0 和正数，所以窗口和不会随边界单调变化，不能直接套只适用于正数数组的滑动窗口。

全部示例

约束

• 1 ≤ nums.length ≤ 2×104。
• -1000 ≤ nums[i] ≤ 1000。
• -107 ≤ k ≤ 107。

一句话总纲：从左到右扫一遍，边走边累加前缀和，并用哈希表记录每个前缀和出现过的次数；每到一个位置，查一次"等于 当前前缀和−k 的历史前缀和出现过几次"，把次数累加进答案，扫完即得结果。

① 核心洞察——区间和就是两个前缀和之差：先约定记号：把 nums[0..j] 的总和记作前缀和 pre[j]，并补一个空前缀 pre[−1]=0（一个元素都没加时的和）。任何子数组的和都能写成 sum(i..j) = pre[j] − pre[i−1]。于是"以 j 结尾、和为 k 的子数组有几个"等价于：j 之前出现过的前缀和里，值等于 pre[j] − k 的有几个。这正是 LC1 两数之和 的哈希套路——边扫边查"能与当前值配出目标的那个数出现过没有"，只是这里要的是出现次数而非下标。

回看暴力慢在哪：枚举所有 (i,j) 再逐段求和是 O(n³)；预处理前缀和数组后区间和 O(1) 可查，仍是 O(n²)——固定右端点 j 后，还要把每个左端点逐一试过。其实每个左端点对应的前缀和在扫描过程中都出现过一次，只是没有按值计数组织起来；把它们存进哈希表，"逐一试左端点"就压缩成一次查表。

② 常见困惑——为什么不能用滑动窗口？看到"连续子数组 + 和"很容易先想滑窗，但本题 nums[i] 可为负：右端纳入新数，窗口和不一定变大；左端移出元素，窗口和也不一定变小。"和超了就缩左、不够就扩右"的判断依据不存在，滑窗这条路被负数堵死。剩下的路只有一条：保留"枚举右端点"，把"数合法左端点"这一步加速到 O(1)。

③ 各个量的身份：

④ 查 prefix−k 还是 prefix+k，不用背：目标等式是 pre[j] − pre[i−1] = k，移项得 pre[i−1] = pre[j] − k——手里拿着当前值，要找的是"比自己小 k"的历史值，所以是减。{0:1} 同样不用背：当 prefix 本身恰好等于 k 时，子数组 [0..j] 明明合法，此时要查的目标值是 prefix−k = 0，对应"一个元素都没加"的空前缀——哈希表里若没有这一条，整类"从头开始"的答案全部丢失。

⑤ 先查后存的顺序：本轮能配对的必须是"j 之前"的前缀。若先把当前 prefix 存进哈希表再查，则 k=0 时目标值 prefix−k 恰好等于 prefix 自己，会查到刚存进去的自己——等于把"长度为 0 的空子数组"数成一个答案。循环体固定为：累加 → 查 prefix−k → 存 prefix。

⑥ 常见困惑——哈希只存次数、不存下标，信息够吗？够。题目只问"有几个子数组"：同一个前缀和值出现 3 次，就是 3 个不同的左端点，每个都独立贡献一个合法子数组——"出现次数"恰好就是要累加的量，位置从头到尾用不上。

⑦ 用原题示例 1 nums=[1,1,1], k=2 走一遍：

起点：prefix=0，prefix_count={0:1}，answer=0。
读 nums[0]=1：prefix=1，查 1−2=−1，0 次；存入后 {0:1, 1:1}。
读 nums[1]=1：prefix=2，查 2−2=0，命中空前缀 1 次——对应子数组 [0..1]，answer=1；存入后 {0:1, 1:1, 2:1}。
读 nums[2]=1：prefix=3，查 3−2=1，命中"读完 nums[0] 那轮存入"的前缀 1——对应子数组 [1..2]，answer=2。
答案 2 ✓；两次命中的历史前缀都严格早于当前位置，⑤的顺序自洽。

nums = [1, 2, 3]，k = 3

第 1 步｜起点：prefix=0，prefix_count={0:1}，answer=0
第 2 步｜读 1：prefix=1，找 -2，未命中              answer=0
第 3 步｜读 2：prefix=3，找  0，命中 [1,2]          answer=1
第 4 步｜读 3：prefix=6，找  3，命中 [3]            answer=2

每次找的是“更早的 prefix-k”；所以本轮必须先查询，再存入当前 prefix。

class Solution:
    def subarraySum(self, nums, k):
        # 1. 空前缀出现一次，用于统计从下标 0 开始的子数组
        prefix_count = {0: 1}
        prefix = 0
        answer = 0

        # 2. 先查询历史 prefix-k，再记录当前 prefix
        for number in nums:
            prefix += number
            answer += prefix_count.get(prefix - k, 0)
            prefix_count[prefix] = prefix_count.get(prefix, 0) + 1

        return answer

时间 O(n)：单趟扫描，每步一次哈希查询 + 一次写入；空间 O(n)：最坏情况下 n+1 个前缀和互不相同，账本存满。高频追问一："能不能把空间压到 O(1)？"一般不能——负数杀死滑窗判据后，必须保留全部历史前缀的计数；只有当 nums 全为正（窗口和随两端移动严格单调）时，才能改用双指针滑窗做到 O(1) 空间。追问二："如果只问'是否存在'而不是'有几个'？"哈希表退化成集合即可，框架不变——计数版与存在版的差别只在 value 存什么。

功能：[1,1,1],2 → 2、[1,2,3],3 → 2；边界：单元素 [3],3 → 1 / [1],0 → 0；特殊：含负数 [1,-1,0],0 → 3、k=0、全为 0 数组（大量子数组）。

考点：前缀和把区间量转成两点之差 + 哈希边扫边数搭档，以及"负数为何杀死滑窗"的判断。通用范式收束：统计满足某个等式的连续区间 → 把区间量改写成两前缀之差，固定右端点、用哈希 O(1) 数出等于 prefix−k 的历史前缀。识别信号：题面出现"连续子数组 + 和恰好等于 / 差为定值 / 能被整除"，且元素含负数或带取模——单调性一失效就该想它。关联：↔ LC1 两数之和（"找 prefix−k"就是两数之和的哈希）、↔ LC437 路径总和 III（同一套前缀和+哈希搬到树上，回溯时要撤销计数）、↔ LC76 最小覆盖子串（同为子串统计，条件单调时才轮到滑窗）。

要完成的任务

给定整数数组 nums 和窗口大小 k。窗口最初覆盖数组最左侧的 k 个元素，此后每次向右移动一格；返回每个窗口中的最大值所组成的数组。

全部示例

约束

• 1 ≤ nums.length ≤ 105。
• -104 ≤ nums[i] ≤ 104。
• 1 ≤ k ≤ nums.length，因此窗口始终有效。

一句话总纲：维护一个存下标的双端队列，保持对应值从队头到队尾递减：每读一个新元素，先从队尾删掉所有值不超过它的旧下标，再把它的下标入队，然后把已滑出窗口的队头删掉；窗口填满后，每走一步，队头下标对应的值就是当前窗口的最大值。

① 核心洞察——一批下标永远当不上最大值，可以当场删除：看窗口里的两个位置 i 和 j，j 在 i 右边（j > i）。若还满足 nums[j] ≥ nums[i]，那么 i 从此出局：窗口是连续区间，今后任何还包含 i 的窗口一定也包含 j，而 j 的值不比 i 小——i 永远轮不到当最大值。把所有这样的出局下标当场删光，幸存下标恰好构成下标递增、值递减的序列，这就是单调队列。（暴力对每个窗口重扫求最大是 O(n·k)，慢就慢在这些注定出局的下标每一轮都被重新比较一遍。）

② 为什么不用堆、为什么队列要双端：想 O(1) 取最大也可以用大顶堆，但窗口滑动时最左元素要离开，堆删不掉任意元素，只能存 (值, 下标) 做惰性删除（取堆顶时发现已滑出窗口才弹），O(n log k) 且实现繁琐——堆的根本问题是保管了所有窗口元素，包括已出局的。单调队列反过来只保留"还有机会"的下标。但下标除了被①的判据删除，还会因滑出窗口而失效：按值的删除发生在队尾（同 LC739 每日温度 的单调栈：新元素清掉所有不比自己大的旧元素），滑出窗口的删除发生在队头——两端都要能删，栈升级成双端队列。

③ 队列里每个位置的身份：

④ 两种删除性质完全不同：队尾删除比的是值——出现了更晚、值又不小于它的元素，它被永久淘汰、永不回归；队头删除比的是下标——它只是滑出了窗口范围，与值的大小无关。

⑤ 常见困惑——队列里为什么存下标、不存值？判"是否滑出窗口"只有下标能回答；只存值时，连相同的值是哪一次出现都分不清。存下标也不损失信息——nums[index] 随时取回值。一份下标，两种用途：比大小用 nums[index]，判滑出用 index 本身。

⑥ 为什么队头永远是窗口最大值：先看删得合不合法：被队尾删除的下标 i，是因为出现了更右、值不小于它的下标 j——今后任何含 i 的窗口都含 j，i 的答案资格被 j 完全顶替，删掉零损失。再看会不会漏：当前窗口真正的最大值下标一定还在队列里——它没滑出窗口，也不可能被队尾删除（它右侧的窗口内没有比它大的值；若曾有相等值把它删掉，留下的那个值相同，答案不变）。队列的值从队头到队尾递减，所以队头就是窗口最大值的下标。与新元素相等的队尾同样可以删（顶替者值相同、更晚滑出），所以比较用 ≤ 更省；写 < 不算错，只是队列里残留无用的重复值。

⑦ 两个边界不用背：窗口覆盖 [right−k+1, right]，队头滑出即 queue[0] < right−k+1，整理成 queue[0] ≤ right−k；又因窗口每步只右移一格、至多送走一个下标，且队内下标严格递增，只需 if 不需 while。第一个填满的窗口右端是 k−1，故从 right ≥ k−1 才开始记答案。

⑧ 用原题示例 nums=[1,3,-1,-3,5,3,6,7], k=3 走一遍（queue 以"下标→值"展示）：

right=0 读 1：队空，入队，queue=[0→1]，窗口未满。
right=1 读 3：队尾值 1 ≤ 3，删下标 0；入队后 queue=[1→3]，窗口未满。
right=2 读 −1：队尾值 3 > −1，直接排到队尾，queue=[1→3, 2→−1]；窗口 [1,3,-1] 的答案＝队头值 3。
right=3 读 −3：排到队尾，queue=[1→3, 2→−1, 3→−3]；队头下标 1 > 3−3=0，未滑出，答案 3。
right=4 读 5：队尾 −3、−1、3 依次 ≤ 5，全部删除，queue=[4→5]；答案 5。
right=5 读 3：排到队尾，queue=[4→5, 5→3]；答案 5。
right=6 读 6：删掉值 3 和 5，queue=[6→6]；答案 6。
right=7 读 7：删掉值 6，queue=[7→7]；答案 7。
结果 [3,3,5,5,6,7] ✓。

注意本例中队头都是先被队尾删除，从没等到滑出窗口。队头滑出的分支用 [7,2,4], k=2 验证：
读 2 时：队尾值 7 > 2，排到队尾，queue=[0→7, 1→2]，队头值 7 是窗口 [7,2] 的答案。
读 4 时：队尾值 2 ≤ 4 被永久删除；4 入队后队头下标 0 满足 0 ≤ 2−2，已滑出窗口，从队头删除，剩 queue=[2→4]，窗口 [2,4] 的答案是 4。
两种删除在同一步先后发生，原因完全不同。

nums = [7, 2, 4]，k = 2        队列从左到右保持递减

第 1 步｜读 7：queue=[7]，窗口还没满
第 2 步｜读 2：queue=[7,2]，窗口 [7,2] 的最大值是 7
第 3 步｜读 4：先从队尾淘汰 2，queue=[7,4]
第 4 步｜窗口右移：7 从队头过期，queue=[4]，最大值是 4

队尾弹出：新值更有竞争力；队头弹出：旧下标已经离开窗口。

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        # 1. queue 存下标，对应值从队头到队尾递减
        queue = deque()
        result = []

        for right, number in enumerate(nums):
            # 2. 淘汰队尾不可能再成为最大值的旧元素
            while queue and nums[queue[-1]] <= number:
                queue.pop()
            queue.append(right)

            # 3. 队头下标离开窗口时，将它移出
            if queue[0] <= right - k:
                queue.popleft()

            # 4. 窗口形成后，队头对应值就是当前最大值
            if right >= k - 1:
                result.append(nums[queue[0]])

        return result

时间 O(n)：内层 while 看似嵌套，但每个下标一生至多入队 1 次、出队 1 次（队尾淘汰或队头过期二选一），全部轮次的弹出总量被 n 界住——摊还分析，不能按"每轮最坏弹 k 个 × n 轮"相乘误判成 O(n·k)：弹出预算是全局共享的 n 个。空间 O(k)：队列只存窗口内的候选下标。高频追问一："什么输入让队列最长/最短？"递减数组队列长到 k（谁也淘汰不了谁，只能等队头逐个过期），递增数组队列始终 1 个（新元素每步淘汰队列里全部旧下标）——两个极端时间都是 O(n)。追问二："堆的 O(n log k) 什么时候反而值得用？"当窗口不再规则滑动，或还要同时查第 2、第 3 大时——单调队列为了 O(n) 把"被压制者"信息永久丢弃，那些场景下丢不得。

功能：[1,3,-1,-3,5,3,6,7],3 → [3,3,5,5,6,7]；边界：k=1（返回原数组）、k=len(nums)（返回单个全局最大）；特殊：递减数组 [5,4,3,2],2 → [5,4,3]、含相同值、含负数。

考点：单调队列的永久淘汰判据、存下标判过期、摊还 O(n)。通用范式收束：滑动区间求极值 → 只维护"还有机会当答案"的单调候选序列；被"更强又更晚离场"者支配的元素当场永久出局。识别信号：定长（或单向伸缩）窗口 + 每步要 max/min；DP 优化里"转移取最近 k 项最值"也是它。关联：↔ LC739 每日温度（单端版：单调栈只有队尾淘汰、没有队头过期）、↔ LC3 无重复最长子串（同一滑窗骨架，维护的是合法性而非极值）、↔ LC42 接雨水（也有单调栈解法，同款"维护候选"思想）。

要完成的任务

给定字符串 s 和 t，在 s 中寻找最短连续子串，使它包含 t 的全部字符以及各自的重复次数。若不存在返回空字符串；测试数据保证非空答案唯一。

“覆盖”只要求字符计数不少于 t，不要求顺序相同；返回的是子串本身，不是长度或下标。

全部示例

约束与进阶

• m == s.length，n == t.length，且 1 ≤ m,n ≤ 105。
• s 和 t 只由英文字母组成，大小写字符彼此不同。
• 若存在符合条件的子串，题目保证最短答案唯一。
• 进阶要求把时间复杂度做到 O(m+n)。

一句话总纲：用两个只前进不后退的指针在 s 上夹出一个窗口：右端不断吞入字符，直到窗口把 t 要求的字符（含重复次数）全部凑齐；一旦凑齐，立刻收缩左端并逐轮登记当前可行窗口，缩到覆盖刚好被破坏再继续右扩；扫完整个 s，登记过的最短窗口就是答案。

① 洞察一——覆盖只朝一个方向变化：先明确"覆盖"的含义：窗口里每种 t 需要的字符，个数都不少于它在 t 中的个数。往窗口加字符只会让计数变大，所以已覆盖的窗口继续右扩永远还是覆盖；从窗口删字符只会让计数变小，所以不覆盖的窗口再怎么右移左端也不会自己变覆盖。这条单调性把搜索空间砍掉一大半：固定左端点时，只有第一个达成覆盖的右端点值得看，再往右全是更长的可行解；而窗口一旦覆盖，就该立刻缩左端，把当前局面下的极小窗口逼出来，缩到刚好破坏覆盖为止。两个端点全程只单向前进——这就是变长滑窗，和 LC3 无重复最长子串 同一副骨架、方向相反：LC3 保持"合法"求最长，本题冲到"可行"再收缩求最短。

回看暴力慢在哪：枚举所有 O(m²) 个子串、每个重数一遍字符是 O(m²·|Σ|)。它慢就慢在没用上①的单调性：明知某窗口已经覆盖，还把同一左端点后面所有更长的子串一个个数了一遍；相邻子串只差一个字符，计数却每次从零重来。

② 洞察二——判"已覆盖"只需要一个数：滑窗每走一步都要问一次"覆盖了吗"。把窗口计数与 t 的计数整表对一遍是 O(|Σ|)，总复杂度带上 |Σ| 因子，进阶要求的 O(m+n) 就没了。关键在于：判覆盖不需要知道每种字符各差多少，只需要知道总共还欠多少个。于是维护两个增量更新的量：一张记录"每种字符还欠几个"的表 need（用 Counter(t) 初始化），和一个总缺口数 missing（初值 len(t)）。每吞入或移出一个字符只改 need 的一项、至多把 missing 加减 1；判覆盖变成一次整数比较 missing == 0。

③ need 的三段身份（同一个计数器，符号不同身份不同）：

④ 两处先后顺序从 missing 的定义直接推出：missing 是"正数 need 之和"，所以它只在某个 need[c] 跨越 0 边界的瞬间变化。纳入 c：跨没跨界要看减 1 之前是否 > 0，故先判 if need[c] > 0: missing −= 1，再 need[c] −= 1；移出 c：要看加 1 之后是否变正，故先 need[c] += 1，再判 if need[c] > 0: missing += 1。两处方向相反但判据同一条——"看变化落在正区间的哪一侧"，不用死记。

⑤ 常见困惑——计数为什么允许为负？无关字符会不会搅乱判定？允许为负正是省掉一切特判的关键。Counter(t) 对无关字符默认计 0：纳入前 need = 0 不满足 > 0，missing 纹丝不动；纳入后 need 转负，含义自动变成"窗口里它多了几个"。将来左缩移出它时 need 从负数加 1，也回不到正数——全程与 missing 绝缘。必需字符的多余份数同理：第二个同种字符进窗只把 need 压到 −1，记下"多一个"，不碰 missing。

⑥ 答案为什么记在收缩循环里：while missing == 0 每一轮的开头，窗口都是一个可行解——先与历史最短比较，再移出左端字符。这样每个"极小可行窗口"（再缩一格就破的窗口）都恰好在被破坏之前登记过，最优解不会漏。

⑦ 用原题示例 1 s="ADOBECODEBANC", t="ABC" 走一遍：起点 need={A:1,B:1,C:1}，missing=3，left=0。

right=0 吞 A：补缺，need[A] 1→0，missing 3→2。
right=1..4 吞 D、O、B、E：B 补缺（missing 2→1）；D/O/E 是无关字符，need 各自 0→−1，missing 不动。
right=5 吞 C：missing 1→0，首次覆盖。登记 "ADOBEC"（长 6）；移出左端 A，need[A] 0→1 回正，missing=1，收缩停止，left=1。
right=6..9 吞 O、D、E、B：第二个 B 进窗时 need[B] 已是 0，不算补缺，missing 保持 1——这正是④里"先判 need[c] > 0 再减"防住的高危一步。
right=10 吞 A：missing→0。收缩依次移出 D、O、B、E（B 的 need 由 −1 回到 0，不回正，missing 不动），窗口缩到 "CODEBA"（长 6）与最短持平、不更新；再移出 C，need[C] 0→1 回正，missing=1，停，left=6。
right=11 吞 N：无关字符，missing 不动。
right=12 吞 C：missing→0，再次收缩。
移出 O、D（need 各自由负回 0，missing 不动），窗口缩到 "EBANC"（长 5），刷新最短。
再移出 E，窗口缩到 "BANC"（长 4），再次刷新。
移出 B：need[B] 0→1 回正，missing=1，收缩停止。
扫描结束，最短登记为 "BANC" ✓，与示例 1 一致。

s = A B A A C，t = "AAC"       need 初始 {A:2,C:1}

第 1 步｜右扩到 C：[A B A A C]  首次覆盖，best="ABAAC"
第 2 步｜移出富余 A：A [B A A C] 仍覆盖，best="BAAC"
第 3 步｜移出无关 B：A B [A A C] 仍覆盖，best="AAC"
第 4 步｜再移出 A： A B A [A C]  缺少一个 A，停止收缩

结果：最短覆盖窗口是下标 [2..4] 的 "AAC"。

from collections import Counter

class Solution:
    def minWindow(self, s, t):
        # 1. need 表示各字符还缺多少；missing 表示总缺口
        need = Counter(t)
        missing = len(t)
        left = 0
        best = (float('inf'), 0, 0)

        # 2. 右扩窗口，只有真正补上缺口时才减少 missing
        for right, char in enumerate(s):
            if need[char] > 0:
                missing -= 1
            need[char] -= 1

            # 3. 已覆盖时持续缩左，并记录更短的合法窗口
            while missing == 0:
                window_length = right - left + 1
                if window_length < best[0]:
                    best = (window_length, left, right)

                leave_char = s[left]
                need[leave_char] += 1
                if need[leave_char] > 0:
                    missing += 1
                left += 1

        # 4. best 未更新说明不存在覆盖窗口
        if best[0] == float('inf'):
            return ""
        return s[best[1]:best[2] + 1]

时间 O(m+n)：建 need 表 O(n)；主循环里 right 走 m 步，left 只增不减也至多走 m 步——内层 while 的总轮数被 left 的总前进量界住，是摊还分析，不能按"每步最坏缩 m 次 × m 步"相乘误判成 O(m²)。空间 O(|Σ|)：计数表至多字母表大小个键。高频追问一："不用 missing，每次覆盖判断遍历 need 表行不行？"正确但每步 O(|Σ|)，总 O(m·|Σ|)，达不到进阶的 O(m+n)——missing 的意义就是把整表比较折叠成一个整数。追问二："为什么滑窗在这里成立、在 LC560 就不行？"本题可行性（覆盖）随右扩单调不减、随左缩单调不增；LC560 元素含负数，"和"没有这种单调性。

功能：s="ADOBECODEBANC",t="ABC" → "BANC"；边界：s=t="a" → "a"、len(s)<len(t) 返回 ""；特殊：t 有重复字符 t="aa"（需两个 a）、无解返回 ""、s 与 t 完全相同。

考点：变长滑窗"右扩到可行 + 左缩到极小"双阶段、need/missing 增量判覆盖、摊还 O(m+n)。通用范式收束：求"最短可行连续区间"且可行性随扩张单调不减 → 变长滑窗：扩右直到可行，立刻缩左并逐轮登记答案，缩破后继续扩右。识别信号：题面出现"最短/最小窗口 + 包含（覆盖）某组字符或满足某计数条件"，且往窗口加元素不会破坏条件。关联：↔ LC3 无重复最长子串（同骨架求最长：保持合法扩右、破坏才缩左）、↔ LC438 找所有异位词（定长版覆盖：计数恰好相等）、↔ LC560 和为K的子数组（条件不单调时滑窗失效，改前缀和+哈希）。

要完成的任务

给定整数数组 nums，从中选择一个至少包含一个元素的连续子数组，使其元素和最大，返回这个最大和。只返回数值，不需要返回子数组下标。

全部示例

约束与进阶

• 1 ≤ nums.length ≤ 105。
• -104 ≤ nums[i] ≤ 104。
• 必须选择至少一个元素，因此全负数组不能把空子数组当成和 0。
• 进阶要求在 O(n) 解法之外，再尝试分治解法。

暴力起手：枚举起点 i、终点 j 的所有子数组求和取最大，配前缀和是 O(n²)（朴素三重循环 O(n³)），在 n ≤ 10⁵ 下超时。慢的根源：以 j 结尾的那批子数组，和"以 j−1 结尾的那批"只差一个 nums[j]——绝大部分求和工作在相邻结尾位置之间被整批重复，却完全没有复用。

① 关键转化——换枚举对象，从"枚举两个端点"到"只枚举结尾"：任何子数组都恰好以某个位置结尾，所以把全部子数组按结尾位置分组：只要知道"必须以 i 结尾的最大子数组和"（记作 current_sum），对所有结尾取最大就是答案。这一步把二维枚举 (i,j) 压成一维状态，是最简的一维 DP；"扫一遍、每个位置维护一个累积量"的思想与 LC238 前缀积 同款，只是这里的累积量允许"断开重开"。

② 递推从直觉推出——以 i 结尾的子数组只有两种形态：要么只含自己 [nums[i]]，要么是"以 i−1 结尾的某段"再接上自己。接上时当然挑最好的那段，而"以 i−1 结尾的最好一段"正是 current_sum 的旧值——于是 current_sum = max(nums[i], current_sum + nums[i])，两个候选恰好对应两种形态，一个不多一个不少。直白判据：旧 current_sum > 0 就是助力、接上；≤ 0 就是拖累、丢弃重开。

③ 两个量的身份（本题最易混）：

④ 常见困惑——递推只有"整段接上"或"完全重开"两个选项，接上前段的一部分呢？不会漏："接上前段的一部分"＝"以 i−1 结尾的某个更短段 + 自己"，而那些更短段全是 current_sum 定义里枚举过的对象，current_sum 已经是它们的最大值——max 只需和这一个代表比较。同理，最优子数组不一定以最后位置结尾也不用怕：best_sum 在每个结尾处都截过流，最优段在它自己的结尾位置被记录——这就是不能只返回最后一个 current_sum 的原因。

⑤ 样例验证关键一步：[-2,1,-3,4,-1,2,1,-5,4] 走到 i=2（值 −3）：max(−3, 1+(−3))=−2，接上比重开好——接上一个负数后 current_sum 变负，但仍是"以 i=2 结尾"里最好的；随后 i=3：max(4, −2+4)=4，负的 current_sum 被果断丢弃重开，此后累加到 [4,-1,2,1] 得 best_sum=6；i=7 时 current_sum 回落到 1，best_sum 锁住 6 不动。

⑥ 正解②：分治（进阶要求）。核心洞察：任何子数组要么完全在左半、要么完全在右半、要么跨过中点——前两类递归求解；跨中点的段必穿过 mid | mid+1 这条缝，可独立拆成"以 mid 结尾的最大后缀和（left_suffix_best）＋以 mid+1 开头的最大前缀和（right_prefix_best）"，各自从缝向外扫一趟即得。三类候选取最大即区间答案。

取舍：Kadane 一趟 O(n)/O(1)，面试首选；分治 O(n log n)/O(log n)，价值在练"跨中点合并"的分治思维，也是线段树维护区间最大子段和的原型。

nums=[-2,1,-3,4,-1,2,1,-5,4]

Kadane 里程碑1  i=0：current_sum=-2，best_sum=-2
里程碑2  i=1：丢弃负前缀，从 [1] 重开；current_sum=1
里程碑3  i=3：再次从 [4] 重开；current_sum=4
里程碑4  i=6：扩成 [4,-1,2,1]；current_sum=best_sum=6
里程碑5  i=8：current_sum=5，但 best_sum 锁住 6

分治顶层 solve(0,8)，middle=4：
左半最优=4，右半最优=4；跨中点左扩峰值=3，右扩峰值=3
合并三类候选：max(4,4,3+3)=6

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 1. 首元素初始化，保证全负数组也必须选一个元素
        current_sum = best_sum = nums[0]

        # 2. 每轮决定接续前段还是从当前值重开
        for value in nums[1:]:
            current_sum = max(value, current_sum + value)
            best_sum = max(best_sum, current_sum)
        return best_sum

# 解法二：分治 O(n log n)（理解分治的经典练习, 比 Kadane 的 O(n) 慢）
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def solve(left_index, right_index):
            # 1. 单元素区间是递归出口
            if left_index == right_index:
                return nums[left_index]

            # 2. 递归求完全位于左右半区的答案
            middle = (left_index + right_index) // 2
            left_best = solve(left_index, middle)
            right_best = solve(middle + 1, right_index)

            # 3. 从中点两侧向外扩，求跨中点答案
            running_sum = 0
            left_suffix_best = float('-inf')
            for index in range(middle, left_index - 1, -1):
                running_sum += nums[index]
                left_suffix_best = max(left_suffix_best, running_sum)

            running_sum = 0
            right_prefix_best = float('-inf')
            for index in range(middle + 1, right_index + 1):
                running_sum += nums[index]
                right_prefix_best = max(right_prefix_best, running_sum)

            # 4. 三类候选覆盖所有连续子数组
            return max(left_best, right_best, left_suffix_best + right_prefix_best)

        return solve(0, len(nums) - 1)

Kadane：时间 O(n)，空间 O(1)，一次扫描且只用两个滚动变量。分治：时间 O(n log n)——递推式 T(n)=2T(n/2)+O(n)（合并时从中点向两侧各扫一趟），每层合计 O(n)、共 O(log n) 层；空间 O(log n)，来自递归调用栈。

高频追问一："要求返回最优子数组的起止下标怎么改？"重开（max 取到 nums[i] 自身）时记录候选起点 start=i；best_sum 被刷新时锁定 (best_start, best_end)=(start, i)。仍是 O(n)/O(1)。追问二："元素以数据流形式一个个到达，还能做吗？"能——Kadane 每步只依赖上一步的 current_sum 与 best_sum，天然在线，O(1) 状态即可持续维护。

功能：[-2,1,-3,4,-1,2,1,-5,4]→6；边界：单元素 [1]→1、单负元素 [-1]→-1；特殊：全负 [-3,-1,-2]→-1（不能返回0，必须选一个元素）、全正 [1,2,3]→6。

考 Kadane / 一维 DP 的状态设计与"何时重开"。通用范式收束：枚举所有区间太贵时，改成只枚举结尾位置、维护"必须以此结尾的最优值"，全局答案对所有结尾取最大——这是"以 i 结尾"型一维 DP 的模板。识别信号：题面出现"连续子数组 + 最大/最小 + 可累积量（和、积）"。关联：↔ LC152 乘积最大子数组（乘法版：负负得正，须同时维护最大与最小）、↔ LC238 除自身以外的乘积（同为"一趟累积量"思想）。

要完成的任务

给定区间数组 intervals，每个元素 [start,end] 表示包含两个端点的闭区间。合并所有重叠区间，返回一组两两不重叠且覆盖范围相同的区间；输入顺序不保证有序。

全部示例

约束

• 1 ≤ intervals.length ≤ 104，且每项长度为 2。
• 0 ≤ start ≤ end ≤ 104。
• 输出区间的顺序按实现产生即可，标准做法按起点升序返回。

暴力起手：任取两个区间判重叠、能并就并；但一次合并可能制造新的重叠（[1,3] 吞掉 [2,6] 之后才够得着 [5,8]），所以只能反复整轮扫描，直到一整轮无事发生，最坏 O(n²) 以上。慢的根源：输入乱序时"和谁重叠"毫无方向，每个区间都要与所有区间比；重叠关系散落全局，没有被组织起来。

① 关键转化——排序把"全局配对"压成"只看邻居"：按起点排序后，可能与当前区间重叠的对象一定紧挨着出现在它前面；更强的性质是：当前区间只需要和"结果里最后一段"比一次（为什么够，见④）。这与 LC15 三数之和 的前置转化同款——花 O(n log n) 买有序性，把全局搜索换成一次线性扫描。

② 三个角色的身份：

③ 判据与更新从直觉推出：
重叠判据 start <= merged[-1][1] 含等号：闭区间在端点相接（[1,4] 与 [4,5] 共享 4）也算重叠，写成严格 < 就漏了这一类。
扩展右端写 max(merged[-1][1], end) 而非直接赋 end：排序只保证 start 有序，end 仍然乱序——当前区间可能被末段完全包含（[1,4] 吃 [2,3]），直接赋值会把右端缩回去。

④ 常见困惑——只和末段比一次，怎么保证不漏掉与更早段的重叠？正面推一遍：merged 里的段两两不相交且按起点递增，所以任何更早段的右端 < 末段的左端 ≤ 末段的右端。若当前 start 大于末段右端，它就更大于所有更早段的右端——一个都够不着，新开即可；若不大于，并入末段即可。末段的右端代表了全部历史，一次比较就够。

⑤ 样例验证：[[1,3],[2,6],[8,10],[15,18]]：读 [2,6]，2 ≤ 3 → 并入，右端取 max(3,6)=6，末段长成 [1,6]；读 [8,10]，8 > 6，且由④，8 也必然越过更早所有段 → 封存 [1,6]、新开 [8,10]。

取舍：排序 O(n log n) 主导，扫描 O(n)；相比暴力反复整轮扫描，排序把"找可合并对象"从全局搜索降成"只看结果末尾"。

输入:   [[1,3],[2,6],[8,10],[15,18]]
排序后: [[1,3],[2,6],[8,10],[15,18]]

里程碑1  结果为空，读 [1,3]：新开 → [[1,3]]
里程碑2  读 [2,6]：2≤3，扩展末尾 → [[1,6]]
里程碑3  读 [8,10]：8>6，新开 → [[1,6],[8,10]]
里程碑4  读 [15,18]：15>10，新开 → [[1,6],[8,10],[15,18]]

最终数轴: 1======6    8==10       15===18

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 1. 按起点排序，让可能重叠的区间连续出现
        intervals.sort(key=lambda interval: interval[0])
        merged = []

        # 2. 只需与已合并结果的最后一段比较
        for start, end in intervals:
            if merged and start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
        return merged

时间 O(n log n)，排序主导；扫描 O(n)。空间 最坏 O(n)，Python 的 Timsort 可能使用线性临时空间；扫描本身只用 O(1) 辅助状态，返回结果另占 O(n)。

高频追问一："为什么只按起点排序就够，end 乱序不用管吗？"不用——end 的乱序由"右端取 max"兜底；同起点的两个区间无论谁先来，后到者都必与先到者重叠并被 max 合并，结果一致，不需要 (start, end) 双关键字。追问二："区间流式到达、不能先整体排序怎么办？"用按起点组织的有序结构（平衡树 / SortedList）维护互不相交的段，每来一个区间向左右两侧局部合并，单次 O(log n + 被合并段数)——即 LC352 数据流区间的做法。

功能：[[1,3],[2,6],[8,10],[15,18]]→[[1,6],[8,10],[15,18]]；边界：单区间 [[1,4]]→[[1,4]]；特殊：仅端点相接 [[1,4],[4,5]]→[[1,5]]（<= 不能写成 <）、被完全包含 [[1,4],[2,3]]→[[1,4]]（终点取 max 才对）、乱序输入。

考"排序+一次扫描"处理区间重叠，以及 <=/取 max 的细节。通用范式收束：散落全局的两两关系（重叠、冲突、相邻），先按一维排序，把"全局配对检查"压成"只与最近的活跃对象比一次"。识别信号：题面出现"区间/时间段 + 重叠/合并/冲突/最少资源"。关联：↔ LC763 划分字母区间（把每个字母的 [首现,末现] 区间做同款合并）、↔ LC189 轮转数组（同属数组顺序/原地处理基本功）；同一套路还可迁移到会议室、插入区间等题。

要完成的任务

给定整数数组 nums 和非负整数 k，把数组整体向右轮转 k 个位置并直接修改 nums。向右轮转一步会把末尾元素移到开头；函数不需要返回新数组。

全部示例

约束与进阶

• 1 ≤ nums.length ≤ 105。
• -231 ≤ nums[i] ≤ 231-1，0 ≤ k ≤ 105。
• 题目鼓励比较至少三种方法，并进一步做到 O(1) 额外空间的原地轮转。

暴力起手：一步一步挪——每次把末尾元素搬到开头，重复 k 次，O(n·k)。慢的根源：每一步全数组搬一遍却只前进一格，同一元素被反复搬运。一次到位的改进是开新数组 new[(i+k)%n]=nums[i]，O(n) 时间，但要 O(n) 额外空间。

① 约束排除法：进阶要求 O(1) 额外空间——新数组法出局；O(n·k) 又太慢——逐步挪出局。剩下的路只有一条：原地、且每个元素只动常数次。已知的两条原地路线：环状替换（沿 i → (i+k)%n 直接把每个元素送到终点，但要按 gcd(n,k) 处理多个置换环，易错）与本题主推的三次翻转。

② 关键转化——轮转＝两个块交换，块交换＝三次翻转：先看目标形态：向右轮转 k 后，数组恰是「后 k 个元素整块搬到前面、前 n−k 个整块搬到后面」。记前段 A＝前 n−k 个、后段 B＝后 k 个，目标就是 A·B → B·A。块交换没有 O(1) 空间的现成原语，但翻转有（首尾双指针交换）；而整体翻转满足恒等式 rev(A·B) = rev(B)·rev(A)——两段位置已经互换，代价是各自内部倒序，再各翻一次抵消即可。这一招在 LC48 旋转图像 升级成二维：旋转 90° ＝ 两次翻转的组合。

③ 每一步后两段的身份（同一段元素，不同时刻形态不同）：以 [1,2,3,4,5,6,7], k=3（A=[1,2,3,4]，B=[5,6,7]）为例：

④ 区间边界与 k%=n 从直觉推出：
k%=n：轮转 n 步回到原样，只有 k mod n 有效；题目允许 k 大于数组长度，必须先消掉整圈。
三段区间：整体 [0,n-1]；第二次翻转的范围就是 B 的新家——B 有 k 个元素、住进前 k 格，故 [0,k-1]；剩余 [k,n-1]。最常见的误代入是把分界写成 n-k——那是向左轮转的分界（左转时搬到后面的是前 k 个）。

⑤ 常见困惑——翻转明明会打乱顺序，为什么翻两次反而"翻对"了？整体翻转同时做了两件事：交换两段位置（想要的）＋颠倒每段内部（副作用）。翻转是自逆操作 rev(rev(X))=X，对每段再各翻一次，恰好只抵消副作用而不动段的位置——三次翻转＝一次换位＋两次消副作用。

⑥ 样例验证关键一步：验证"整体翻转后 B 恰好占住前 k 格"：rev([1,2,3,4,5,6,7]) = [7,6,5,4,3,2,1]，前 3 格 [7,6,5] 正是 rev([5,6,7])=rev(B)，后 4 格 [4,3,2,1] 正是 rev(A)——与②的恒等式逐位吻合；再翻前 3 格、后 4 格，即得 [5,6,7,1,2,3,4]。

取舍：三次翻转 O(n)/O(1)，实现稳定，面试默写首选；额外数组法同为 O(n) 时间但多 O(n) 空间；环状替换也是 O(1) 空间且搬运次数最少，却要处理 gcd(n,k) 个置换环。

nums=[1,2,3,4,5,6,7], k=3

里程碑1  初始分段：[1,2,3,4 | 5,6,7]
里程碑2  整体翻转：[7,6,5 | 4,3,2,1]
里程碑3  翻前 k 个：[5,6,7 | 4,3,2,1]
里程碑4  翻后 n-k 个：[5,6,7 | 1,2,3,4] ✓

每次交换使用 Python tuple swap，右侧旧值会先整体保存，
不存在“写一半导致旧值丢失”的可观察中间态。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        length = len(nums)
        k %= length                         # 1. 去掉完整轮转圈数

        def reverse(left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        # 2. 整体翻转交换两段位置
        reverse(0, length - 1)
        # 3. 分别翻转两段，恢复各自内部顺序
        reverse(0, k - 1)
        reverse(k, length - 1)

时间 O(n)，三次翻转合计约 n 次交换（2n 次元素写入）。空间 O(1)，纯原地。

高频追问一："还有别的 O(1) 空间做法吗？"环状替换：从每个未访问的起点沿 i → (i+k)%n 搬运一圈，共形成 gcd(n,k) 个环，总写入恰好 n 次，搬运最省，但环的起点计数与终止判断易错，面试默写推荐三次翻转。追问二："能少于 n 次元素移动吗？"不能——k%n≠0 时每个元素的终点都不是原位，n 次写入是下界；三次翻转约 2n 次写入，是为实现简单付出的常数代价。

功能：[1,2,3,4,5,6,7],k=3→[5,6,7,1,2,3,4]；边界：单元素 [1],k=0、k=0 不变；特殊：k>n 如 [1,2],k=3（k%=n 后为1）、k==n（回到原样）。

考原地 O(1) 空间的翻转技巧与 k%=n 取模。通用范式收束：原地做"整块搬移/换序"时，用翻转这种自逆原语组合——整体翻转换段序，分段翻转消除内部倒序的副作用。识别信号：题面出现"原地 + O(1) 空间 + 旋转/整块移动"。关联：↔ LC48 旋转图像（二维版的"翻转组合出旋转"）、↔ LC56 合并区间（同属数组原地/顺序处理）。

要完成的任务

给定整数数组 nums，返回同长度数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外所有元素的乘积。要求 O(n) 时间，并且不能使用除法。

全部示例

约束与进阶

• 2 ≤ nums.length ≤ 105。
• -30 ≤ nums[i] ≤ 30；任意前缀或后缀的乘积都保证可用 32 位整数表示，且每个 answer[i] 也保证在 32 位整数范围内。
• 进阶要求除输出数组外仅使用 O(1) 额外空间；返回的输出数组不计入额外空间。

暴力起手：对每个 i 遍历一遍其余元素相乘，O(n²)。慢的根源：相邻两个位置的答案共享绝大部分因子（answer[2] 和 answer[3] 的乘数只差两个元素），但每次都从头乘，公共部分完全没有复用。

除法法为什么不行：先算总积再 answer[i]=总积/nums[i]，看似 O(n)，但含 0 就崩——总积变 0，0 所在位置还要算 0/0；就算统计 0 的个数分类讨论能绕过去，题目也明令禁止除法。这条路的价值是逼出正解的问法：不用除法，怎么"去掉自己"？

① 关键转化——"除自身"＝"左半 × 右半"：自己就是一条分界线：answer[i] = (i 左边全部的积) × (i 右边全部的积)，两半都不含自己，拼起来恰好是"除自身以外的一切"。于是问题退化成标准子问题：给每个位置预计算前缀积和后缀积——这与 LC53 的前缀和同款，只是加法换乘法。

② 空间优化——输出数组先当左积容器：朴素做法开 prefix[]、suffix[] 两个数组，O(n) 额外空间。观察：左积可以直接写进输出数组 answer（题目声明输出不计入额外空间）；右积每个位置只用一次，用完即弃——不需要整个数组，一个滚动变量 right_product 从右往左边走边乘就够了。

③ 各个量的身份（本题核心：同一个量在不同时刻身份不同）：

④ "先用后更新"的顺序从身份表直接推出：右扫循环体两句话的顺序不可交换——answer[i] *= right_product 必须发生在 right_product *= nums[i] 之前，因为乘给 answer[i] 的必须是"不含自己"的右积；更新放在后面，正是完成「i 的右积」→「i−1 的右积」的身份切换。左扫同理：answer[i] = answer[i-1] * nums[i-1] 用的是 nums[i-1] 不是 nums[i]——旧值 answer[i-1] 是「i−1 的左积」，把 i−1 自己纳入后才是「i 的左积」，自己永远不进自己的积。

⑤ 含 0 为什么天然正确：不用任何特判——0 落在谁的左半或右半，那一半的积自然是 0；唯独 0 自己的位置，左右两半都不含这个 0，拼出来恰是"其余元素之积"。用 [1,0,3] 验证：answer[0]＝左空(1)×右积(0×3=0)＝0；answer[1]＝1×3＝3；answer[2]＝(1×0)×1＝0 → [0,3,0] ✓。分界线切法自动把 0 分派到了正确的一侧。

⑥ 用样例走关键一步：[1,2,3,4] 左扫后 answer=[1,1,2,6]。右扫到 i=2：此刻 right_product=4（只含 nums[3]，不含 nums[2]=3），answer[2]=2×4=8；随后 right_product=4×3=12，完成向「下标 1 的右积」的变身。

nums = [1,2,3,4]
answer[i] = (i 左边全部的积) × (i 右边全部的积)，自己是分界线，两半都不含自己

以 i=2 为例：   [1  2] │ 3 │ [4]
               左半积=2  ↑  右半积=4   →  answer[2] = 2 × 4 = 8
                       自己不参与

第一趟·从左往右：answer 先只装「左积」
  answer[0]=1（左边为空＝乘法单位元 1）
  递推 answer[i] = answer[i-1] × nums[i-1]
       └ 旧值「i-1 的左积」，纳入 nums[i-1] 自己后变身「i 的左积」
  nums    [1, 2, 3, 4]
  answer  [1, 1, 2, 6]   ← 每格＝左边全部的积

第二趟·从右往左：right_product 滚动装「右积」，乘进 answer 拼合两半
  i=3: answer[3] ×= 1 → 6    然后 right ×= 4 → 4
  i=2: answer[2] ×= 4 → 8    然后 right ×= 3 → 12
  i=1: answer[1] ×= 12 → 12  然后 right ×= 2 → 24
  i=0: answer[0] ×= 24 → 24
  answer  [24, 12, 8, 6] ✓

「先用后更新」的瞬间放大看（i=2）：
  乘入前  right_product = 4        ＝「下标2 的右积」（不含 nums[2]=3）
  乘入后  right_product = 4×3 = 12 ＝「下标1 的右积」（3 对下标1 属于右边）
  同一个变量，一句话之隔身份不同——两句顺序反了，3 就乘进了自己的答案

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n   # 此阶段身份：左积容器，还不是答案

        # 1. 左扫：旧值 answer[i-1]=「i-1 的左积」，纳入 nums[i-1] 后变身「i 的左积」
        for i in range(1, n):
            answer[i] = answer[i - 1] * nums[i - 1]   # 用 nums[i-1] 不是 nums[i]：自己不入积

        # 2. 右扫：right_product 滚动维护「i 的右积」，乘入 answer 拼合左右两半
        right_product = 1   # 最右位置右边为空＝乘法单位元 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right_product   # 先用：此刻 right_product 还不含 nums[i]
            right_product *= nums[i]     # 后更新：纳入自己，变身「i-1 的右积」
        return answer

时间 O(n)：两趟线性扫描。空间 O(1) 额外：输出数组按题目声明不计，除它之外只有 right_product 一个变量。高频追问一："能不能一趟扫完？"不能——answer[i] 需要 i 右边全部元素的信息，任何单向一趟扫到 i 时右边还没看过，两趟是信息依赖决定的下界。追问二："如果允许除法？"仍要按 0 的个数分类（无 0→总积/自己；恰一个 0→仅 0 位置为其余积；两个以上→全 0），并不比两趟扫更简单。

功能：[1,2,3,4]→[24,12,8,6]；边界：最短两元素 [2,3]→[3,2]（各自的答案就是对方）；特殊：含一个 0 [1,0,3]→[0,3,0]（唯独 0 位置非零，验证⑤的分界线逻辑）、含两个 0 [0,0,3]→[0,0,0]（每个位置的左右两半至少含一个 0）、含负数 [-1,1,0,-3,3]→[0,0,9,0,0]（0 位置＝(-1)×1×(-3)×3=9，符号自然正确）。

考"除自身＝左半×右半"的分解、前缀/后缀积预计算、复用输出数组+滚动变量把空间压到 O(1)。通用范式：答案需要来自两侧的信息时，各自方向预计算一趟再拼合。关联：↔ LC53 最大子数组和（前缀累积量思想的加法版）、↔ LC152 乘积最大子数组（同是乘积，正负翻转要同时维护最大最小）、↔ LC42 接雨水（每格积水＝min(左侧最大, 右侧最大)−自身，同款"两侧预计算再拼合"）。

要完成的任务

给定未排序整数数组 nums，返回其中没有出现的最小正整数。0、负数和大于数组长度的数都可能出现在输入中；目标复杂度为 O(n) 时间、O(1) 额外空间。

全部示例

约束

• 1 ≤ nums.length ≤ 105。
• -231 ≤ nums[i] ≤ 231-1。
• 数组可含重复值，算法需要原地工作且不能通过额外集合保存所有元素。

暴力起手：两条直觉路——排序后从 1 开始逐个核对，O(n log n)；或把所有数塞进哈希集合，再从 1 起试第一个不在集合里的正整数，O(n) 时间 O(n) 空间。慢/费的根源：排序把力气花在"完全排好序"上，其实只需要知道 1..n 里谁出现过；哈希集合花整整 O(n) 空间，只为回答"值 v 出现过没有"这一种成员查询。

① 约束排除法——两个约束合起来只留一条路：题目要 O(n) 时间——排序出局；又要 O(1) 额外空间——哈希集合、布尔标记数组全出局。但成员查询总得有地方记录，O(1) 额外空间下唯一可写的 O(n) 存储，就是输入数组自己。出题人的箭头指向：把数组自身当哈希表用。这与 LC238 的"输出数组先当左积容器"同一精神——题目已经交到你手里的数组，就是免费存储。

② 先把答案范围钉死（抽屉原理）：长度为 n 的数组就算装满，也最多覆盖 1..n 这 n 个正整数，此时答案是 n+1；只要有缺，答案 ≤ n。所以答案必在 [1, n+1]，负数、0、大于 n 的值全是与答案无关的"垃圾值"。这一步同时回答了"桶只开 n 个够不够"——够，恰好一格对应一个候选值。

③ 先写"理想方案"——放宽空间约束，人人都会的签到表：由②，最后一步必然是"从 v=1 起逐个问：v 出现过吗？"，所以真正需要的只是一张 n 格签到表：第 v 格记录"值 v 出现过没有"，每格 1 bit。若允许 O(n) 空间，谁都会写——开布尔数组，扫一遍，对每个落在 [1,n] 的值 x 置 seen[x] = True，再从 1 起找第一个 False。注意"值当下标"在这一步已经出现且毫不费解：seen[x] = True 就是拿值 x 当下标去找它专属的格子。难点只剩一个——这张签到表的空间从哪来。

④ 关键转化——签到表画在 nums 自己身上，交换代替写标记：由①，O(1) 空间下唯一可写的 n 格存储就是 nums 的下标 0..n−1，让下标 i 充当"值 i+1 的签到格"。新问题：格子里住着原始数据，直接写标记会把还没签到的值覆盖掉——信息永久丢失。破局是把"写标记"改成"搬位置"：签到动作＝把值 v 本人交换到它专属的格子 v−1，此后 nums[v-1] == v 恒真——它就是 seen[v] = True 在 O(1) 空间下的无损等价物：交换不销毁任何数，只让两个数换位置；被换出的旧住户回到手上继续投递（这正是后面必须 while 的来源）。归位结束后数组本身就成了 1..n 的签到表，再扫一遍找第一个没签到的格子。看到"值域（或有效值域）恰是 1..n"就要条件反射"值当下标"：LC287 用它把数组读成隐式链表找重复，本题用它做原地桶签到——同一个信号，两种用法。

⑤ 各个量的身份（同一个格子在不同时刻身份不同）：

⑥ 循环写法从直觉推出：
为什么是 value−1：桶从下标 0 起、值从 1 起，错位一格——值 1 住下标 0。
为什么用 while 不是 if：交换是双向搬家——把手里的值送回家的同时，家里的旧住户被换到手上；新住户可能也不在家，得继续投递，直到手上是垃圾值或已就位的值。
为什么停机条件是 nums[target_index] == nums[index]：目标桶已放着相同值（重复值）时再换只是原地打转；若把循环条件写成 nums[index] != index+1，两个相同值会互换到天荒地老。

⑦ 常见困惑——for 里套 while，还是 O(n) 吗？是。每发生一次交换，必有一个值回到自己家、且从此再不离家（想把它换走，手里必须持有同值，而停机条件恰好在此 break），所以全部 while 的交换总次数 ≤ n——预算全局共享，与 LC84 "每根柱子至多弹出一次"同款摊还。另一个隐忧"垃圾值会不会捣乱"也不会：垃圾值只会滞留在无人认领的格子里，而无人认领的格子恰是缺失值的位置，扫描读到垃圾值正好触发失配返回。

⑧ 样例验证关键一步：[3,4,-1,1]：index=0 手持 3 → 送回下标 2，换回 −1（垃圾，停），得 [-1,4,3,1]；index=1 手持 4 → 送回下标 3 换回 1，手持 1 继续 → 送回下标 0 换回 −1（垃圾，停），得 [1,-1,3,4]——一趟 while 连续归位两个值，正是"必须 while"的现场。扫描：下标 0 签到 1 ✓；下标 1 期望 2 却是 −1 → 返回 2。垃圾值 −1 恰好停在缺失值 2 的格子上。

回看推导链（每一步都被上一步逼出来）：答案必在 [1, n+1] → 只需一张 n 格签到表 → O(1) 空间下签到表只能借 nums 自身的下标 → 借来的格子里有原始数据、不能覆盖 → 用交换代替写标记 → 换出来的值还得继续归位 → 必须 while。正解不是灵光一现，而是被约束逼出的唯一活路；面试时讲清这条链，比背对交换代码更加分。

nums=[3,4,-1,1], n=4；值 value 应在下标 value-1

里程碑1  初始：[3,4,-1,1]
里程碑2  i=0，把 3 交换到下标2：[-1,4,3,1]
里程碑3  i=1，把 4 交换到下标3：[-1,1,3,4]
里程碑4  i=1，换入的 1 继续归位：[1,-1,3,4]
里程碑5  扫描：位置0正确；位置1期望2却是-1 → 返回2

交换使用 tuple swap，旧值先整体保存；真正的风险是换入新值后
若只用 if 就不会继续归位，因此代码必须使用 while。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        length = len(nums)

        # 1. 把 [1,length] 内的值反复交换到 value-1 位置
        for index in range(length):
            while 1 <= nums[index] <= length:
                target_index = nums[index] - 1
                if nums[target_index] == nums[index]:  # 重复值已占目标桶，避免死循环
                    break
                nums[index], nums[target_index] = nums[target_index], nums[index]

        # 2. 第一个值与下标不匹配的位置就是最小缺口
        for index, value in enumerate(nums):
            if value != index + 1:
                return index + 1
        return length + 1

时间 O(n)。for 套 while 不能按"每轮最坏 × n 轮"相乘：每次交换都让一个值永久归位，家只有 n 个，所以全部 while 的交换总预算 ≤ n（摊还），加上两趟线性扫描仍是 O(n)。空间 O(1)，原地交换。

高频追问一："嵌套循环为什么还是线性？"标准回答即上面的摊还论证——看交换总量的全局预算（每次交换消灭一个"未归位"），不看单轮最坏。追问二："不用交换还有别的 O(1) 做法吗？"符号标记法：先把 ≤0 与 >n 的垃圾值统一改写成 n+1，再对每个出现的 v ∈ [1,n] 把 nums[v-1] 取负作"出现"标记，最后返回第一个仍为正数的下标 +1；同为 O(n)/O(1)，但读值要用 abs 防重复取负，且同样依赖"允许改动数组"。

功能：[3,4,-1,1]→2；边界：[1,2,0]→3、单元素 [1]→2、[2]→1；特殊：全负/越界 [-5,-2]→1、含重复 [1,1]→2（用 nums[nums[i]-1]!=nums[i] 判重防死循环）、[7,8,9,11,12]→1。

考"原地哈希/桶归位"以及 O(1) 空间约束下的抽屉原理。通用范式收束：O(n) 时间 + O(1) 空间双约束 → 输入数组自身是唯一可用的 O(n) 存储；有效值域被抽屉原理压进 [1,n] → 值当下标，把成员信息写回数组。识别信号：长度 n 的数组、答案或关键值被限制在 1..n(+1) 之内、还禁止额外空间。关联：↔ LC287 寻找重复数（同款"值当下标"，读成隐式链表找环）、↔ LC238 除自身以外的乘积（同款"把题目给的数组当免费存储"）、↔ LC189 轮转数组（同为 O(1) 空间原地操作）。

要完成的任务

给定 m×n 整数矩阵 matrix。若某个元素原本为 0，就把它所在的整行和整列全部改为 0；必须直接修改输入矩阵，不返回另一张矩阵。

判断依据必须来自原始矩阵中的 0，不能让置零过程中产生的新 0 再触发额外行列。

全部示例

约束与进阶

• m == matrix.length，n == matrix[0].length，且 1 ≤ m,n ≤ 200。
• -231 ≤ matrix[i][j] ≤ 231-1。
• 直观方案需 O(mn) 标记空间，行列集合需 O(m+n)；进阶要求常量额外空间。

一句话总纲：先备份"首行、首列自己是否含 0"两个布尔 → 再扫描内部，把"第 i 行要清""第 j 列要清"记到首列、首行的格子上 → 标记打完后统一回填内部，最后按备份收尾首行首列。

① 暴力起手——"边扫边清"不只是慢，而是错：最直观的写法是扫到 0 就当场清掉它所在的行和列。但你写下的新 0 会被后续扫描当成"原始 0"再次触发清零，连锁扩散（坑①有最小反例）。

这一步逼出了本题所有解法的公共骨架：必须分成"先只读、记下哪些行列要清"和"再统一写"两个阶段。最朴素的记法是两个集合 rows/cols：时间 O(m·n)、额外空间 O(m+n)。时间已经最优——每格至少读一次才能找全原始 0——所以出题人卡的不是时间，是空间：进阶要求 O(1)。

② 约束排除法——O(1) 空间逐个杀死直觉方案：

方案一·visited 副本矩阵：O(m·n) 空间，直接出局。

方案二·rows/cols 集合：O(m+n)，也出局。

方案三·魔法数：把置零过程先写成某个"矩阵里不会出现的值"，最后统一换回 0——但值域覆盖完整的 32 位整数，不存在保证不冲突的空闲值，出局。

三条路堵死后只剩一个方向：标记信息不放矩阵外面，就只能放矩阵里面。问题变成——放在哪儿，才不会毁掉还没读到的原始信息？

③ 关键转化——集合的本质是 m+n 个布尔位，矩阵里恰好有现成的容器：把 rows/cols 拆开看，它就是 m 个"第 i 行要不要清"加 n 个"第 j 列要不要清"的布尔位。而首列恰好有 m 个格、首行恰好有 n 个格：让"第 i 行要清"写成 matrix[i][0]=0、"第 j 列要清"写成 matrix[0][j]=0——首列当行标记数组、首行当列标记数组。

代价：首行首列自己的原始值会被标记覆盖。补偿：首行/首列"整条要不要清"各自只需一个布尔就能描述——在动手打标记之前先算好，存进 first_row_zero/first_col_zero。O(m+n) 个布尔就这样被压缩成"借用的格子 + 2 个变量"。

④ 四个阶段的顺序是被依赖关系逼出来的，不用背：

阶段一·先备份两个布尔：打标记会往首行首列写 0，之后再也分不清"本来就有的 0"和"标记写的 0"，所以备份必须发生在一切写入之前。

阶段二·扫内部打标记：只扫 i,j≥1，遇原始 0 就写 matrix[i][0]=0 和 matrix[0][j]=0。

阶段三·回填内部：必须等标记全部打完再动手，否则又回到"边读边写"的污染老路。

阶段四·首行首列最后清：它们是标记区，提前整清会抹掉标记位，回填内部时就无据可查（坑③的反例正是这么错的）。

一句话总结：同一块内存既当数据又当标记，使用顺序就必然有严格先后。

⑤ 常见困惑——回填时读到 matrix[i][0]==0，怎么区分它是"原始 0"还是"标记写的 0"？不用区分。如果它是原始 0，第 i 行本来就该整行清零——原始语义和标记语义在这一格说的是同一句话，两种 0 的结论一致。

真正会产生歧义的只有"首行/首列自身要不要整条清"，而那已经被两个布尔提前备份。这也解释了标记区为什么选首行首列而不是随便哪一行：只有它们的"整条清不清"恰好能各压缩成一个布尔。

⑥ 用原题示例 1 走一遍：[[1,1,1],[1,0,1],[1,1,1]]，唯一原始 0 在 (1,1)。

备份：首行 [1,1,1]、首列 [1,1,1] 都不含 0，两个布尔均 False。
打标记：扫内部读到 (1,1) 的 0，写 matrix[1][0]=0（行标记）、matrix[0][1]=0（列标记）。
回填内部：(1,1)、(1,2) 被行标记清零，(2,1) 被列标记清零，(2,2) 两个标记都没亮、保持 1。
收尾：两个布尔均 False，首行首列不整清，得 [[1,0,1],[0,0,0],[1,0,1]]，与示例 1 输出一致 ✓。

注意标记写下的两个 0 留在了成品里且恰好正确：(1,0) 位于要清的行 1 上、(0,1) 位于要清的列 1 上——标记格永远落在"被清行/列与首行首列的交点"，标记本身就是答案的一部分，不需要擦除。

例 matrix（3 行 4 列，唯一原始 0 在 (1,2)；*0* = 刚写入的标记位）

① 初始，先保存首部原始状态：first_row_zero=False，first_col_zero=False
        列0  列1  列2  列3
   行0 [ 1    1    1    1 ]
   行1 [ 1    1    0    1 ]   ← (1,2) 是原始 0
   行2 [ 1    1    1    1 ]

② 扫到 (1,2)=0，先写行标记 matrix[1][0]=0    ‖ 瞬时态：列标记尚未写
   行0 [ 1    1    1    1 ]
   行1 [*0*   1    0    1 ]   ← 行1 的标记位亮起
   行2 [ 1    1    1    1 ]

③ 再写列标记 matrix[0][2]=0    ‖ 两类标记齐全
   行0 [ 1    1   *0*   1 ]   ← 列2 的标记位亮起
   行1 [*0*   1    0    1 ]
   行2 [ 1    1    1    1 ]

④ 第二遍扫内部：所在行或所在列有标记的内部格清零
   行0 [ 1    1   *0*   1 ]
   行1 [ 0    0    0    0 ]   ← 行1 整行清（行标记）
   行2 [ 1    1    0    1 ]   ← (2,2) 单点清（列2 标记）

⑤ 两个首部标志均为 False → 首行/首列不再整清，上图即最终结果

最终 [[1,1,0,1],[0,0,0,0],[1,1,0,1]]：行1 靠"行标记"整清、(2,2) 靠"列标记"单清，两条标记各司其职 ✓。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row_count, col_count = len(matrix), len(matrix[0])

        # 1. 标记区将覆盖旧值，先保存首行首列的原始信息
        first_row_zero = any(matrix[0][col] == 0 for col in range(col_count))
        first_col_zero = any(matrix[row][0] == 0 for row in range(row_count))

        # 2. 扫描内部；行标记与列标记是两次独立写入
        for row in range(1, row_count):
            for col in range(1, col_count):
                if matrix[row][col] == 0:
                    matrix[row][0] = 0
                    matrix[0][col] = 0

        # 3. 只根据标记回填内部，暂不改首行首列
        for row in range(1, row_count):
            for col in range(1, col_count):
                if matrix[row][0] == 0 or matrix[0][col] == 0:
                    matrix[row][col] = 0

        # 4. 最后依据最初保存的状态处理首行首列
        if first_row_zero:
            for col in range(col_count):
                matrix[0][col] = 0
        if first_col_zero:
            for row in range(row_count):
                matrix[row][0] = 0

时间 O(m·n)：打标记、回填各扫一遍，每格常数次读写；这也是时间下界——每格至少读一次才能找全原始 0。空间 O(1)：标记借用首行首列，额外只有两个布尔。高频追问一："如果不要求 O(1)，你会怎么写？"答两个集合 rows/cols，O(m+n) 空间、没有阶段顺序陷阱，工程上更推荐——先说清这个取舍再写 O(1) 版是加分项。追问二："能不能把新写的 0 先标成特殊值、最后统一换回？"不通用：值域覆盖完整 32 位整数，不存在保证不冲突的魔法数；Python 里塞 None 是利用动态类型钻空子，换成静态类型语言即失效。

功能：[[1,1,1],[1,0,1],[1,1,1]]→[[1,0,1],[0,0,0],[1,0,1]]；边界：单行 [[1,0,3]]→[[0,0,0]]、单列；特殊：0 在首行/首列 [[0,1],[1,1]]→[[0,0],[0,1]]（考验 first_row/first_col 逻辑）、全 0、无 0 不变。

考"原地标记、避免读写污染"与首行首列复用。通用范式收束："必须先读完全部输入才能开始写"的原地题，把 O(m+n) 级的标记压进输入自身的冗余空间；代价是标记区原始信息要提前备份、各阶段顺序被依赖关系锁死。识别信号：题面同时出现"原地修改"＋"修改会连锁触发新的修改条件"，或明写"进阶：常量空间"。关联：↔ LC41 缺失的第一个正数（同款"把标记信息塞回输入数组自身"）、↔ LC48 旋转图像（同为矩阵原地 O(1) 改写）、↔ LC54 螺旋矩阵（同类二维遍历）。

要完成的任务

给定 m×n 整数矩阵 matrix，从左上角开始，按照顺时针螺旋顺序访问每个元素一次，返回访问顺序组成的数组。输入矩阵不需要被修改。

全部示例

约束

• m == matrix.length，n == matrix[i].length，且 1 ≤ m,n ≤ 10。
• -100 ≤ matrix[i][j] ≤ 100。

一句话总纲：先用 top / bottom / left / right 四条边界框住"还没读的矩形"→ 再一圈圈按"顶行→右列→底行→左列"读一条边、收一条边 → 当边界交错（矩形为空）时，结果数组就是答案。

① 暴力起手 + 费的根源：最贴近题意的做法是真的"走"：保持一个方向前进，每走一步输出一格，撞到边界或撞到走过的格就右转，用 visited 布尔矩阵判重。时间 O(m·n) 没问题，费在空间：O(m·n) 的 visited 记录的是"哪些格走过了"。

但螺旋走过的区域根本不是任意形状——剥掉外圈之后，剩下的永远是一个规则矩形。用 m·n 个布尔去描述一个 4 个数字就能确定的矩形，这就是浪费的根源，也是正解的入口。

② 关键转化——不记"走过哪儿"，改记"还剩哪儿"：把视角从"访问过的格子集合"切换成"未访问的矩形区域"。矩形只需四条边界描述：top / bottom / left / right（都是闭区间行列号）。每输出完一条边，就把对应边界向内收一格——"走螺旋"退化成"反复剥矩形的四条边"，visited 整个省掉。这与二分、双指针是同一族思想：用少量边界变量维护"候选区域"，每步让它严格缩小。

为什么只有底边、左边要守卫，顶边、右边不用？从执行顺序推：进入本圈时 while 刚确认过 top<=bottom and left<=right，走顶行、右列用的是"新鲜担保"；但走完这两条边后 top 和 right 已经收缩过，剩余矩形可能已被掏空（单行、单列时正是如此），担保过期——所以后两条边动身前必须重新验一次。守卫不是模板咒语，是"边界中途变过、担保过期要重验"的必然结论。

倒序 range 从"从哪走到哪"推：底边是从右往左读第 bottom 行：起点列 right、终点列 left，Python 的 range 不含 stop，所以写 range(right, left-1, -1)；左列同理是 range(bottom, top-1, -1)。别背方向口诀，问自己"这条边从哪个角走到哪个角"即可现场写出。

用样例验证守卫真的在拦：单行 [[1,2,3]]。

进圈走顶行：输出 1,2,3，top 收成 1。
走右列：range(1,1) 为空，安全。
走底边前：top=1>bottom=0，第一个守卫把底边拦下。
若没有它，底边会按 range(1,-1,-1) 把 2、1 倒着再读一遍。

matrix=[[1,2,3],[4,5,6],[7,8,9]]，边界 (top,bottom,left,right)=(0,2,0,2)
记号：▸ = 本轮读取的格，· = 之前已读过的格

① 走顶行 →（读 1,2,3），top 0→1
   ▸1 ▸2 ▸3
    4  5  6      result=[1,2,3]
    7  8  9      剩余矩形 = 行1..2 × 列0..2

② 走右列 ↓（读 6,9），right 2→1
    ·  ·  ·
    4  5 ▸6      result=[1,2,3,6,9]
    7  8 ▸9      剩余矩形 = 行1..2 × 列0..1

③ 守卫 top<=bottom 通过，走底行 ←（读 8,7），bottom 2→1
    ·  ·  ·
    4  5  ·      result=[1,2,3,6,9,8,7]
   ▸7 ▸8  ·      剩余矩形 = 行1..1 × 列0..1

④ 守卫 left<=right 通过，走左列 ↑（读 4），left 0→1
    ·  ·  ·
   ▸4  5  ·      result=[1,2,3,6,9,8,7,4]
    ·  ·  ·      剩余矩形 = 行1..1 × 列1..1（只剩中心）

⑤ 新一圈走顶行（读 5），随后边界交错，退出
    ·  ·  ·
    · ▸5  ·      result=[1,2,3,6,9,8,7,4,5] ✓
    ·  ·  ·

结果 [1,2,3,6,9,8,7,4,5]。第 6 步两个 if 双双拦下——若少了它们，中心 5 那圈会把底行/左列重复读。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 1. 四条边界框住尚未访问的矩形
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        result = []

        # 2. 每轮按上、右、下、左收完一圈
        while top <= bottom and left <= right:
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top += 1

            for row in range(top, bottom + 1):
                result.append(matrix[row][right])
            right -= 1

            # 3. 收缩后再判断，防止单行或单列被重复读取
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    result.append(matrix[bottom][col])
                bottom -= 1
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    result.append(matrix[row][left])
                left += 1
        return result

时间 O(m·n)，每个元素恰好写入结果一次。空间 O(1) 额外（不计输出）：四个边界变量替代了整张 visited 矩阵。高频追问一："不用 visited，怎么论证不重不漏？"答不变式——任何时刻 [top,bottom]×[left,right] 恰好等于"未输出集合"：每条边输出后立即收缩边界维持不变式，两个守卫保证矩形空了就停止输出。追问二："螺旋矩阵 II（LC59，把 1..n² 按螺旋序填入矩阵）怎么做？"同一套四边界模板，把"读 matrix"换成"写递增计数器"即可——模板的价值就在读写通用。

功能：3×3→[1,2,3,6,9,8,7,4,5]；边界：单行 [[1,2,3]]→[1,2,3]、单列 [[1],[2],[3]]→[1,2,3]；特殊：长条形 [[1,2,3,4],[5,6,7,8]]（考验两个 if 边界判断）、1×1 [[7]]→[7]。

考四边界收缩与"担保过期要重验"的守卫条件。通用范式收束：遍历中不断缩小的区域若始终保持规则形状（矩形/区间），就用少量边界变量代替 visited 集合，遍历退化为"反复剥边"。识别信号：按几何顺序访问或生成矩阵（螺旋、按层剥圈、之字形），或题面暗示"从外圈到内圈"。关联：↔ LC48 旋转图像（同为方向/下标操控，也按圈处理）、↔ LC73 矩阵置零（同类二维遍历控制）。

要完成的任务

给定 n×n 整数矩阵 matrix，把它表示的图像顺时针旋转 90°。必须直接修改原矩阵，不能分配另一张矩阵承接旋转结果；函数无需返回矩阵。

全部示例

约束

• n == matrix.length == matrix[i].length，1 ≤ n ≤ 20。
• -1000 ≤ matrix[i][j] ≤ 1000。
• 矩阵保证为正方形，且必须原地旋转。

一句话总纲：先沿主对角线转置——把每一行"躺倒"成同编号的列；再把每一行左右翻转——把列的左右次序倒过来。两步做完，矩阵就是顺时针旋转 90° 的结果；全程只有成对交换，天然原地。

① 暴力起手——先想清楚"每个格子要去哪"：记矩阵边长为 n，盯住第 0 行。顺时针转 90° 后，它原封不动地竖在了最后一列，自上而下顺序不变。

推广开来：原第 i 行整行搬到新矩阵的第 n-1-i 列；行内排在第 j 个的元素，搬过去后从上往下数还是第 j 个。写成公式就是 new[j][n-1-i] = old[i][j]。照这个映射另开一张矩阵逐格搬，时间 O(n²)——每格至少动一次，时间已是下界。但另开一张矩阵要 O(n²) 空间，被题目的原地要求判死。卡点全在空间。

② 约束排除法——原地为什么不能直接按公式写：沿用同一公式在原矩阵上写，matrix[j][n-1-i] = matrix[i][j] 会覆盖 (j,n-1-i) 里还没搬走的旧值（坑③有完整反例）。

出路有两条。其一：找出"互相顶替"的四个格子做循环置换，一次转四格——可行，但下标公式一长串，现场容易写错。其二更省心：把旋转拆成若干次"成对互换"——一对格子互换时先存后写，谁也不覆盖谁，交换天然原地。这正是原地约束指向的方向。

③ 关键转化——转置＋行翻转，从"第 0 行去哪了"推出来，不用背：

第一步·先转置：沿主对角线交换 (r,c)↔(c,r)，原第 i 行躺倒成第 i 列，行内顺序恰好变成自上而下——"行变列"这一大步完成了。

第二步·找差距：目标要求原第 0 行去最后一列，转置只把它送到了第 0 列——列的左右次序整体反了。

第三步·每行左右翻转：把列序整体倒过来，第 0 列换到第 n-1 列，恰好补齐差距。

用下标复核整条链：转置 (i,j)→(j,i)，行翻转 (j,i)→(j,n-1-i)，复合正是目标 new[j][n-1-i]=old[i][j] ✓。

④ 上三角范围从"每对只能换一次"推：转置的本体是"对称对 (r,c) 与 (c,r) 互换"。若内层 col 从 0 扫全行，每一对会在 (r,c) 和 (c,r) 两处各被碰到一次、交换两次＝原样放回。所以内层从 row+1 起、只扫上三角，每对恰好交换一次；对角线 (r,r) 是自己和自己换，天然不用碰。

⑤ 常见困惑——"转置、行翻转、上下翻转"能组合出顺/逆时针，现场怎么分辨？不背对照表，用"第 0 行去哪了"验证一步：顺时针要求第 0 行去最后一列——转置（送到第 0 列）＋行翻转（列序倒置→最后一列）✓；换成转置＋上下翻转，动的是行序不是列序，第 0 行留在第 0 列，得到的是逆时针 90°。先翻转后转置同样会串向——顺序和轴向共同决定旋向，拿一个具体元素走一遍即可分辨。

⑥ 用原题示例 1 走一遍：[[1,2,3],[4,5,6],[7,8,9]]，全程盯第 0 行 [1,2,3]。

转置：第 0 行躺倒成第 0 列（自上而下 1,2,3），矩阵变为 [[1,4,7],[2,5,8],[3,6,9]]。
逐行翻转：[1,4,7]→[7,4,1]、[2,5,8]→[8,5,2]、[3,6,9]→[9,6,3]。
第 0 行果然到了最后一列（自上而下仍是 1,2,3），结果 [[7,4,1],[8,5,2],[9,6,3]]，与示例 1 输出一致 ✓。

例 matrix=[[1,2,3],[4,5,6],[7,8,9]]，转置只碰上三角三对：(0,1) (0,2) (1,2)
记号：▸ = 本轮刚被交换写入的格；tuple swap 先存后写，无“半次交换”丢值态

① 初始
        列0  列1  列2
   行0 [ 1    2    3 ]
   行1 [ 4    5    6 ]
   行2 [ 7    8    9 ]

② 转置第一对 (0,1)↔(1,0)：2 与 4 互换
   行0 [ 1   ▸4    3 ]   ← 每对只在上三角遍历中被碰到一次，不会再换回去
   行1 [▸2    5    6 ]
   行2 [ 7    8    9 ]

③ 再换 (0,2)↔(2,0)、(1,2)↔(2,1)，转置完成；对角线 1,5,9 全程不动
   行0 [ 1    4   ▸7 ]
   行1 [ 2    5   ▸8 ]   ← 原第 0 行 [1,2,3] 已躺倒成第 0 列（自上而下 1,2,3）
   行2 [▸3   ▸6    9 ]

④ 逐行左右翻转（行内对称位互换），得到最终结果
   行0 [ 7    4    1 ]
   行1 [ 8    5    2 ]   ← 原第 0 行竖到最后一列，自上而下仍是 1,2,3 ✓
   行2 [ 9    6    3 ]
   顺时针 90° 结果 [[7,4,1],[8,5,2],[9,6,3]]，与示例 1 输出一致

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        size = len(matrix)

        # 1. 只交换上三角，确保每个对称位置恰好处理一次
        for row in range(size):
            for col in range(row + 1, size):
                matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col]

        # 2. 转置后逐行左右翻转，得到顺时针 90° 结果
        for row in matrix:
            row.reverse()

时间 O(n²)：转置碰上三角约 n²/2 对，逐行翻转每行 n/2 对交换，均为常数次访问；每格至少动一次，这已是下界。空间 O(1)：全程成对交换，无辅助矩阵。高频追问一："能不能一趟完成、不做两次扫描？"能——四格循环置换 (i,j)→(j,n-1-i)→(n-1-i,n-1-j)→(n-1-j,i)，只遍历左上四分之一区域、每次转 4 格；总移动次数更少但仍是 O(n²)，且下标公式极易写错，面试先给转置＋翻转、被追问再升级是稳妥策略。追问二："旋转 180° / 逆时针 90° 呢？"180°＝行翻转＋上下翻转（不需转置）；逆时针 90°＝转置＋上下翻转——现场用"第 0 行去哪了"推，不用背。

功能：3×3→[[7,4,1],[8,5,2],[9,6,3]]；边界：1×1 [[5]]→[[5]] 不变；特殊：2×2 [[1,2],[3,4]]→[[3,1],[4,2]]、4×4（验证转置 j>i 不重复交换，否则转回去）。

考"把旋转分解为对称交换的复合"与上三角遍历细节。通用范式收束：O(1) 空间的下标重排题，把目标置换分解成若干次"成对互换"（翻转/转置）的复合——互换天然原地，复合的顺序与轴向用一个具体元素的去向来验证。识别信号：原地旋转/轮转/镜像类题面，或明写"不得使用额外矩阵"。关联：↔ LC189 轮转数组（一维同款：三次翻转拼出轮转）、↔ LC73 矩阵置零（矩阵原地 O(1) 技巧）、↔ LC54 螺旋矩阵（二维下标映射与控制）。

要完成的任务

给定 m×n 整数矩阵 matrix 和整数 target，判断 target 是否出现在矩阵中。每一行都从左到右非递减，每一列都从上到下非递减；这不保证按行拼接后整体有序。

全部示例

约束与保证

• m == matrix.length，n == matrix[i].length，且 1 ≤ m,n ≤ 300。
• -109 ≤ matrix[i][j], target ≤ 109。
• 每行从左到右非递减、每列从上到下非递减；元素是否重复不影响算法。

一句话总纲：站上矩阵的右上角——那个位置的值是本行最大、又是本列最小 → 每比较一次：比 target 大就排除一整列（左移一格），比 target 小就排除一整行（下移一格）→ 撞上 target 返回 True，走出边界返回 False。

① 暴力起手——慢在两条有序性没用上：全矩阵线性扫 O(m·n)，"行有序""列有序"两个条件一个都没用上。

升级一步：对每一行二分 target，O(m·log n)——用上了"行内有序"，但"列也有序"仍然闲置：每行的搜索互相独立，行与行之间的大小关系没有传递任何信息。要更快，就必须找到一个能同时动用两条有序性的比较位置——这是正解的入口。

② 关键转化——找一个"比较一次就能砍掉一整块"的出发点：候选自然是矩阵的四个角，逐个检验从它出发的两个前进方向：

左上角：向右变大、向下也变大——value<target 时右和下都有嫌疑，一个方向都排除不了。

右下角：向左变小、向上也变小，对称地失效。

右上角：向左变小、向下变大——两个方向单调性相反，比较结果天然二选一：value>target 说明本列往下只会更大，整列出局、左移；value<target 说明本行往左只会更小，整行出局、下移。

左下角：向右变大、向上变小，同样单调相反，可对称实现。

结论：可用的出发点必须是"两个方向单调性相反"的角。选定右上角后，每次比较都保证消去一整行或一整列——O(m+n) 就是这么来的。

③ 为什么不重不漏——从不变式推：初始时剩余矩形是整个矩阵，不变式显然成立；每次左移/下移排除的那一列/行都已被证明不含 target，所以 target 若存在仍在缩小后的矩形里。循环结束只有两种方式——命中返回 True，或矩形缩空（row==m 或 col<0）返回 False，不重不漏。

④ 常见困惑——行列都有序，为什么不能整体二分做到 O(log(m·n))？整体二分要求"逐行拼接后全局有序"，即每行开头不小于上一行结尾——那是 LC74 的前提。本题只保证行内、列内各自有序：题面矩阵第 1 行末尾是 19，第 2 行开头是 3，拼起来立刻乱序。对任意单点做一次比较，能排除的只是一个角块，剩余区域是 L 形而不是"矩形的一半"，标准二分砍不下去——所以本题的主流最优就是 O(m+n) 阶梯法。

⑤ 用原题示例 1 走一遍（找 target=5）：从右上角 (0,4) 出发。

(0,4)=15，15>5：第 4 列出局，左移到 (0,3)。
(0,3)=11，11>5：第 3 列出局，左移到 (0,2)。
(0,2)=7，7>5：第 2 列出局，左移到 (0,1)。
(0,1)=4，4<5：第 0 行出局，下移到 (1,1)。
(1,1)=5：命中，返回 True。

路径 15→11→7→4→5，四次比较砍掉三列一行；每一步之后剩余区域仍是矩形，当前位置始终是它的右上角，身份表全程适用。

题面 5×5 矩阵找 target=5，从右上角 (0,4) 出发
记号：▸ = 当前所在格，(k) = 第 k 步足迹，· = 已被排除的格

① 起点 (0,4)=15：本行最大、兼本列最小，一次比较必砍掉一整行或一整列
         列0   列1   列2   列3   列4
   行0 [  1    4    7   11  ▸15 ]   ← 15>5：第 4 列往下只会更大，整列出局
   行1 [  2    5    8   12   19 ]
   行2 [  3    6    9   16   22 ]
   行3 [ 10   13   14   17   24 ]
   行4 [ 18   21   23   26   30 ]

② 连续三次“大→左移”：15>5、11>5、7>5，第 4、3、2 列依次整列出局
   行0 [  1   ▸4  (3)  (2)  (1) ]   ← 足迹(1)(2)(3)；现站 (0,1)=4，4<5
   行1 [  2    5    ·    ·    · ]
   行2 [  3    6    ·    ·    · ]      · 区域＝已排除：这三列剩余部分的
   行3 [ 10   13    ·    ·    · ]        最小值（列顶）都 > 5
   行4 [ 18   21    ·    ·    · ]

③ “小→下移”：4<5 说明第 0 行往左只会更小，整行出局，落到 (1,1)=5 命中
   行0 [  ·  (4)  (3)  (2)  (1) ]   ← 第 0 行整行出局
   行1 [  2   ▸5    ·    ·    · ]   ← (1,1)=5==target，返回 True ✓
   行2 [  3    6    ·    ·    · ]
   行3 [ 10   13    ·    ·    · ]      未排除区域收缩为行1..4 × 列0..1，
   行4 [ 18   21    ·    ·    · ]      ▸ 始终是它的右上角（不变式成立）

足迹路径 15→11→7→4→5：四次比较砍掉三列一行，总步数不超过 m+n。

路径 15→11→7→4→5：前三步各砍掉一列、第四步砍掉一行，5 步命中，共走不超过 m+n 格。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 1. 从“向左变小、向下变大”的右上角开始
        row, col = 0, len(matrix[0]) - 1

        # 2. 每轮依据比较结果排除一整列或一整行
        while row < len(matrix) and col >= 0:
            value = matrix[row][col]
            if value == target:
                return True
            if value > target:
                col -= 1
            else:
                row += 1
        return False

时间 O(m+n)：row 只增、col 只减，row 最多加 m 次、col 最多减 n 次，总步数不超过 m+n。空间 O(1)：只有两个指针。高频追问一："能不能更快，比如 O(log(m·n))？"整体二分不行——逐行拼接后不是全局有序（见思路段的困惑），单点比较排除不掉一半；面试口径 O(m+n) 即主流最优，关键是答出"每步必砍一整行或一整列"的论证。追问二："和 LC74 的区别？"74 额外保证每行开头大于上一行结尾，可摊平成一维直接二分 O(log(m·n))；本题条件更弱——先辨认矩阵属于哪种有序，再选算法。

功能：target=5→True；边界：目标位于左下角或右上角、单行或单列矩阵；特殊：不存在 target=20→False（走出边界）、小于全体最小 target=0→False、大于全体最大。

考"利用双向有序性选枢纽角、每步排除一整行/列"。通用范式收束：在部分有序的结构里搜索，先找一个"比较一次就能整块排除"的极值位置（行最大兼列最小），让搜索域每步严格缩小且始终保持规则形状。识别信号：行、列分别有序但整体不保证有序的查找/统计题（找第 k 小、统计不超过 x 的元素个数是同款阶梯走法）。关联：↔ LC74 搜索二维矩阵（整体有序，摊平直接二分——先分清两题前提再动手）、↔ LC33 搜索旋转排序数组（同为"利用局部有序性每步砍掉一块"）、↔ LC54 螺旋矩阵（同为受控的二维行走）。

要完成的任务

给定两个单链表的头节点 headA 与 headB，返回两条链表开始相交的第一个节点；若没有公共节点则返回 null。相交按节点对象相同判断，不是节点值相等。

输入字段与返回值

intersectVal 只是评测页面展示交点值；skipA、skipB 表示从两条链表头分别走多少步到交点，这三个量都不会传给函数。函数实际只接收两个头节点，且返回后链表结构必须保持不变。

示例 1

示例 2

示例 3

约束与保证

• A、B 的节点数分别为 m、n，且 1 ≤ m,n ≤ 3×10⁴。
• 节点值满足 1 ≤ Node.val ≤ 10⁵；0 ≤ skipA ≤ m，0 ≤ skipB ≤ n。
• 若 intersectVal==0 则两链表不相交；否则它等于 listA[skipA] 与 listB[skipB] 的值。
• 题目保证链表无环，且调用结束后原结构不可被破坏。进阶目标是 O(m+n) 时间、O(1) 额外空间。

一句话总纲：让两个指针分别从两条链的头同时出发、同速前进；谁先走完自己那条链，就从另一条链的头接着走。两条拼接路线一样长，所以若相交，第二趟必然同时踩到交点；若不相交，则同时落在 None——两种结局都靠"相等"退出循环。

① 暴力起手：对 A 的每个节点，把 B 从头到尾扫一遍，看有没有同一个对象，O(m·n)。慢的根源：两条链一旦相交，交点之后整段节点完全共享——每轮重扫都在重新验证这段"早已注定相同"的尾巴，共享结构这条信息一次都没被复用。

② 约束排除：顺着"记住见过谁"的直觉，把 A 的全部节点对象放进哈希集，再扫 B，第一个落在集合里的就是交点——O(m+n) 时间，但要 O(m) 空间。进阶要求 O(1) 空间，把"用容器记忆"这条路整个杀掉。不能靠记忆，就只能靠指针走路的方式本身携带信息。

③ 关键转化——用换路补平路程差：先给三段路起名：A 独有段长 x、B 独有段长 y、共享段长 s；再命名两个游标——pointer_a 从 headA 出发、pointer_b 从 headB 出发。两指针各走各的会永远错位：一个在第 x 步到交点，另一个在第 y 步到，时刻不同。改成换路：pointer_a 走完 A 后从 B 头继续，pointer_b 走完 B 后从 A 头继续。两条拼接路线的总长同为 x+s+1+y（各含一次 None 停留）——路程相等、同时出发、同速前进，则第二次经过交点必然同时。和 LC142 一个味道：不去测量差距，而是让双方把彼此的差距互相走掉。

④ 为什么必须"落到 None 才切"：读者直觉是"走到尾节点就该跳对面了"。但 None 这一步不是浪费：它让两条路线各含恰好一次停留，总步数才严格相等。更致命的是，不相交时全靠"双方同时落在 None"这个唯一等点退出循环——在尾节点提前切，不相交的两个指针永远错着相位打转，死循环。

⑤ 常见困惑——会不会在交点之前"碰巧相等"？不会。相等要求是同一对象，而交点之前 pointer_a 只可能站在某条链的独有段上，pointer_b 站在另一条的独有段上，独有段之间没有共享对象。第一趟里若两人同时进入共享段，只可能因为 x=y——那时第一个共同点恰是交点，提前返回也正确。

⑥ 用原题示例 1 走一遍：A=4→1→8→4→5，B=5→6→1→8→4→5，从节点 8 起共享（x=2、y=3、s=3），两条拼接路线各长 2+3+1+3=9 步。

第 1 轮末：pa=1（A 独有段），pb=6。
第 2 轮末：pa=8——第一次路过交点，但 pb 才走到 1，错过不算。
第 3~4 轮末：pa 走过共享段的 4、5；pb 走 8、4，始终慢一拍。
第 5 轮末：pa=None（停留一步），pb=5（共享段尾）。
第 6 轮末：pa 换到 B 头 5，pb=None。
第 7~8 轮末：pa 走 6、1；pb 换到 A 头，走 4、1。
第 9 轮末：pa=8，pb=8——同一对象，返回节点 8 ✓。第一趟错过、第二趟路程对齐后必然同到。

共享结构（c 只存在一个对象）：
A: a1 --------\
                c -> None
B: b1 -> b2 --/

里程碑1  起点：pa=a1，pb=b1
里程碑2  A 先耗尽：pa=None，pb=c
里程碑3  两边完成换路：pa=b2，pb=a1
里程碑4  同步命中：pa=c，pb=c ✓

pa 路线: a1 -> c -> None -> b1 -> b2 -> c
pb 路线: b1 -> b2 -> c -> None -> a1 -> c

class Solution:
    def getIntersectionNode(self, headA, headB):
        # 1. 两指针分别从两条链出发
        pointer_a, pointer_b = headA, headB

        # 2. 到 None 后换到另一条链；相交时同点退出，不相交时同为 None
        while pointer_a is not pointer_b:
            pointer_a = pointer_a.next if pointer_a else headB
            pointer_b = pointer_b.next if pointer_b else headA

        return pointer_a

时间 O(m+n)，两指针各走一遍两链表；空间 O(1)，只用两个指针。高频追问一："不换路，先各自数长度、长链先走差值行不行？"——行，三趟扫描同样 O(m+n)/O(1)；换路法只是把"对齐长度差"编码进路线里，省掉一趟计数，两种都该会讲。追问二："会不会死循环？"——不会：两条拼接路线都是有限长 x+s+1+y，最晚在共同终点 None 处相等退出，轮数上界约 m+n+2。

功能：A、B 在中段相交返回该结点；边界：其中一条为空返回 None、相交点即为某条的头；特殊：完全不相交（两指针同时落到 None，循环靠 pa is pb 终止不会死循环）。

考查双指针抵消长度差、对象身份 vs 值相等的区分。收束成通用范式：两条路径长短不一时，让双方各走"自己的路 + 对方的路"，总路程相等即自动同步到汇合点。识别信号：两条链/序列尾部共享结构、求汇合点、还限 O(1) 空间——先想"拼接换路"，再想"数长度对齐"。关联：↔ LC141 环形链表（同为"用走路方式编码信息"的双指针）、↔ LC206 反转链表（基础指针操作）。

要完成的任务

给定单链表头节点 head，把每条 next 边反向，并返回反转后的新头节点；空链表仍返回 null。

输入与输出

输入、输出都是链表头节点。题面中的数组只是按 next 顺序展示节点值，不是函数参数。

示例 1

示例 2

示例 3

约束

• 链表节点数在 [0,5000] 内。
• -5000 ≤ Node.val ≤ 5000。

暴力起手：把所有节点压栈再按出栈顺序重接，或抄出值数组倒着建新链——都能反转，但要 O(n) 额外空间。费的根源：反转本质只是把每条 next 边就地掉头，掉头某个节点时需要知道的只有"它的前驱是谁"这一条 O(1) 信息，栈却把它存了 n 份。

① 关键转化——逐边掉头：扫描到某个节点时只干一件事：把它的 next 从"指后继"改写成"指前驱"。要安全完成这一笔，恰好需要两个帮手：前驱是谁（用 previous 记住，否则掉头没目标）、后继是谁（改写会覆盖 current.next，先存进 next_node，否则余链失联）。于是自然长出三指针滚动结构——不是背出来的，是"这一笔要覆盖谁"逼出来的。

② 循环不变量串起全程：任意时刻整条链被分成两段——previous 领着的已反转段 + current 领着的原序段，两段合起来节点一个不少。循环体四行的顺序由"谁会被覆盖"唯一决定：current.next 是唯一会被写坏的数据，所以第一行必须先读它（next_node = current.next）；随后 current.next = previous 掉头；最后两指针前移。

③ 递归版——信任后段已完工：reverseList(head.next) 返回后，后段已反转成 new_head→…→head.next，且 head.next 此刻正是反转段的尾。于是 head.next.next = head 把自己挂到段尾后面，再 head.next = None 抹掉旧边、让自己成为新尾。new_head 一路原样上传——因为原尾就是全局新头，每层都不该动它。

④ 常见困惑——为什么返回 previous 不是 current？循环退出条件是 current 变 None：最后一个真实节点在退出前那一轮已经完成掉头、变成了 previous。current 此刻是"链外"的空位，previous 才是原尾＝新头。

⑤ 用样例验证一轮：1→2→3 走到处理节点 2 那一轮：开局 previous=1（段 1→None）、current=2。先存 next_node=3；写 2.next=1 得段 2→1→None；前移后 previous=2、current=3。中途 3 始终被 next_node/current 拎着，没有任何节点失联。

解法① 迭代，1 -> 2 -> 3 -> None

帧1  初始：prev=None | cur=1 -> 2 -> 3
帧2  保存 next_node=2，再写 1.next=None：
      1 -> None | next_node=2 -> 3   （余链由 next_node 保住）
帧3  反转 2 后：prev=2 -> 1 | cur=3
帧4  反转 3 后：prev=3 -> 2 -> 1 | cur=None

解法② 递归回溯时的短环：
帧1  出口 head=3：3 -> None
帧2  写 3.next=2 后：2↔3（临时短环）；清 2.next 后：3->2
帧3  写 2.next=1 后：1↔2（临时短环）；清 1.next 后：3->2->1

class Solution:
    def reverseList(self, head):
        previous, current = None, head

        # 1. 每轮先保存后继，再让当前结点掉头
        while current:
            next_node = current.next        # 掉头前保住余链
            current.next = previous
            previous, current = current, next_node

        # 2. current 已到空，previous 正好是原尾
        return previous

# 解法二：递归（先反转后段，回溯时掉头）
class Solution:
    def reverseList(self, head):
        # 1. 空链或单结点已经完成反转
        if not head or not head.next:
            return head

        # 2. 先反转后段，回溯时把当前结点接到末尾
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None                  # 清旧边，否则当前结点与后继成环
        return new_head

时间 O(n) 遍历一遍；空间 迭代 O(1)，递归 O(n)（调用栈深度=链长）。高频追问一："本题 n 最大 5000，递归版在 Python 里安全吗？"——默认递归深度限制约 1000，n=5000 会 RecursionError；生产和大 n 场景选迭代，这是选迭代为首选的硬理由，不只是风格偏好。追问二："能不能省掉 next_node 只用两根指针？"——不能：覆盖 current.next 之前必须有人记住余链入口；Python 的元组同步赋值只是把三个引用写在一行，本质仍是三个。

功能：1->2->3 → 3->2->1；边界：空链表返回 None、单结点返回自身；特殊：确认原头结点 next 最终为 None（否则成环）。

考查三指针原地操作、先存后继的意识，是链表面试的基石。收束成通用范式：原地改写指针＝每一笔写入前，先保存将被覆盖的引用；用"已处理段/未处理段"这条不变量贯穿循环。识别信号：任何要求重排链表连接（反转/交换/分组）的题，落笔前先问一句"这次写 next 会覆盖谁"。24/25/234 都以本题为公共子过程。关联：↔ LC25 K个一组翻转（分段套用本反转）、↔ LC234 回文链表（反转后半段比对）、↔ LC24 两两交换。

要完成的任务

给定单链表头节点 head，判断从头到尾读出的节点值序列是否为回文，返回布尔值。

输入与输出

数组表示法按链表顺序列出节点值；回文要求正向与反向序列完全相同。

示例 1

示例 2

约束

• 节点数满足 1 ≤ n ≤ 10⁵。
• 0 ≤ Node.val ≤ 9。
• 进阶目标是 O(n) 时间和 O(1) 额外空间。

一句话总纲：先用快慢指针定位链表中点；再把从中点开始的后半段原地反转；最后从原头与反转段新头两端同步比值——短的那端走完且全部相等，即是回文。

① 暴力起手：把节点值依次倒进数组，再用首尾双指针判回文——O(n) 时间但 O(n) 空间。费的根源：回文比对真正缺的只是"后半段能倒着读"这一个能力，前半段本来就能正着走；数组却把整条链都复制了一遍，冗余的恰是不需要复制的前半。

② 约束排除：进阶要求 O(1) 空间，数组、栈、递归缓存全部出局。单链表天生不能倒着走——想倒着读后半段，唯一的路是把后半段物理反转（LC206 原封复用）。

③ 关键转化：回文 ⇔ 前半正读 == 后半倒读。于是拆成三个已学的子问题。先找中点：设两个游标 fast、slow 同从头出发，fast 每轮 2 步、slow 每轮 1 步——fast 到尾时 slow 恰好走了半程、停在中点（LC141 家族的另一用法）。再从 slow 起反转后半（LC206）。最后双指针两端同步比值。

④ 循环条件从两种停法推出：while fast and fast.next 覆盖两种收尾——奇数长 fast 停在尾节点（fast.next 为 None 退出），偶数长 fast 直接变 None 退出；两种情形 slow 分别落在正中点和右中点，正好都是"该开始反转的位置"。

⑤ 常见困惑——奇数长的中点要不要跳过？不用，也不要手动跳。本写法从 slow 开始反转，奇数长时中点被划进反转段：比对的最后一轮是"中点和它自己"（同一对象）相比，必然相等；随后 right 走到 None 自然退出。任何"跳过中点"的特判反而制造错位（见坑③）。

⑥ 用原题示例 1 走一遍：1a→2a→2b→1b（值相同的节点用 a/b 区分对象）。

找中点第 1 轮：slow=2a，fast=2b。
找中点第 2 轮：slow=2b，fast 越过尾变 None——退出，slow 停在右中点 2b。
反转从 2b 起的后半：得 right_head = 1b→2b。
比对第 1 轮：left=1a，right=1b，值相等 ✓。
比对第 2 轮：left=2a，right=2b，值相等 ✓。
right 走到 None，循环结束，返回 True。奇数长的情形（如 1→2→3→2→1）只多一轮"中点和自己比"，其余完全相同。

例：1a -> 2a -> 3 -> 2b -> 1b -> None（a/b 表示不同对象）

帧1  快慢定位：slow 依次 1a→2a→3，停在中点 3
帧2  保存 2b 后写 3.next=None：
      左路 1a->2a->3->None | 余链 2b->1b->None（没有丢链）
帧3  后半反转稳定：right_head=1b->2b->3->None
帧4  比对：1a=1b，2a=2b，最后 3=3（同一中点对象）
帧5  right 耗尽，返回 True

class Solution:
    def isPalindrome(self, head):
        # 1. 快慢指针定位中点或右中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 原地反转从 slow 开始的后半段
        right_head = None
        while slow:
            next_node = slow.next
            slow.next = right_head
            right_head, slow = slow, next_node

        # 3. 以后半段长度为准，从两端同步比对
        left, right = head, right_head
        while right:
            if left.val != right.val:
                return False
            left, right = left.next, right.next
        return True

时间 O(n)：找中点 + 反转 + 比对各 O(n)；空间 O(1)，只在原链表上反转。高频追问一："这个解法改动了输入链表，怎么补救？"——比对结束后把 right_head 段再反转一次、接回前半末尾即可还原，多一趟 O(n) 不改变复杂度；面试主动提这一句是加分点。追问二："用栈存前半再弹出来比不行吗？"——功能正确，但栈是 O(n) 额外空间，达不到进阶要求；它只是数组法换了容器。

功能：偶数 1->2->2->1 True、非回文 1->2->3 False；边界：空/单结点均 True；特殊：奇数长时反转段包含中点，最后中点与自身比较。

考查快慢指针找中点 + 反转的组合。收束成通用范式：需要倒序访问单链表的一段 → 物理反转那一段（用完可再反转还原），而不是复制它；本题＝141 的快慢定位 + 206 的反转 + 双指针比对三件套。识别信号：回文/对称/首尾配对 + 链表 + O(1) 空间限制。关联：↔ LC206 反转链表（后半段反转）、↔ LC141 环形链表（同为快慢指针）、↔ LC148 排序链表（另一种找中点口径，坑②的对照）。

要完成的任务

给定链表头节点 head，判断沿 next 不断前进是否会再次到达已经访问过的节点；有环返回 true，无环返回 false。

字段含义

pos 表示尾节点连接到链表中第几个节点（从 0 开始），-1 表示尾节点指向 null。它只用于描述测试数据，不会传入函数。

示例 1

示例 2

示例 3

约束

• 节点数在 [0,10⁴] 内，-10⁵ ≤ Node.val ≤ 10⁵。
• pos 为 -1 或链表中的有效下标。
• 目标是使用 O(1) 额外空间。

暴力起手：哈希集记录访问过的节点对象，再次遇到同一对象即有环——O(n) 时间，但 O(n) 空间。费的根源：为了回答"走没走过"，把每个走过的节点都存了一份；而题目要的只是一个布尔结论。

① 约束排除：进阶要求 O(1) 空间，哈希集出局；"改节点值做标记"也不该用（破坏输入，且值域内任何标记值都可能与真实值撞车）。不能留记忆，"有没有绕圈"这条信息就只能藏在两个游标的相对位置里。

② 关键转化——从"记忆判重"换成"追及判环"：有环 ⇔ 一直走永远遇不到 None ⇔ 在环上跑的两个人如果速度不同，快的必然一圈圈追上慢的。让 fast 每轮 2 步、slow 每轮 1 步：双双入环后，fast 每轮净追近 1 格，环上间距逐轮减 1，有限轮内必到 0（相遇）；无环则 fast 先撞到 None，循环自然结束。

③ "移动后再判"从初始状态推出：slow、fast 同从 head 出发，初始化的相等是出发点重叠，不是追上；只有移动之后的相等才唯一对应"fast 绕圈追上了 slow"。所以判定必须放在两次移动之后。

④ 常见困惑——fast 一次跳两格，会不会直接跨过 slow 永不相遇？不会。设某轮开始时 fast 在环上落后 slow 的距离为 d（沿前进方向），一轮后距离变 d−1：净接近恰好 1 格，距离序列是 d, d−1, …, 1, 0，逐一递减、不会从 1 跳到 −1。步幅选 1/2 正是为了让相对速度恰为 1，"跨过"在数学上不可能。

⑤ 用样例走一遍：3→2→0→-4，-4 指回 2：第 1 轮 slow=2、fast=0；第 2 轮 slow=0、fast=2；第 3 轮 slow=-4、fast=-4（fast 走 2→0→-4）——同一对象，返回 True。若把 -4 的回边去掉，fast 会在第 2 轮跳到 None，条件 fast and fast.next 失败退出，返回 False。

结构：3 -> 2 -> 0 -> -4
             ^             |
             +-------------+     （-4.next 回到同一个结点 2）

帧1  初始化：slow=3， fast=3（尚未移动，不判命中）
帧2  第1轮后：slow=2， fast=0
帧3  第2轮后：slow=0， fast=2
帧4  第3轮后：slow=-4，fast=-4，同一对象 ✓

若无环：fast 每步领先, 会先走到 fast.next=None, 循环条件失败退出, 返回 False。

class Solution:
    def hasCycle(self, head):
        slow = fast = head

        # 1. fast 可安全走两步时，再按 1/2 步幅移动
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            # 2. 必须移动后再判对象身份，避免初始化时误判
            if slow is fast:
                return True
        return False

时间 O(n)：无环 fast 走 n/2 轮撞尾；有环时 slow 入环那一刻 fast 已在环内、落后间距至多 环长−1，每轮缩 1，slow 在环内走不满一圈就被追上。空间 O(1)。高频追问一："为什么相遇保证发生在 slow 入环后第一圈内？"——就用上面这句间距论证，它同时给出 O(n) 的严格上界。追问二："步幅换成 1 和 3 行不行？"——不保证：相对速度变 2，环上间距按 2 递减，若环长为偶数且初始间距为奇数，间距永远跳不到 0；1/2 步幅让相对速度恰为 1，是"必然相遇"的最稳选择。

功能：有环 True、无环 False；边界：空链表/单结点无环 False、单结点自环 True；特殊：环入口即头结点。

考查 Floyd 判环、为什么快慢必相遇。收束成通用范式：不许用额外空间记忆时，用两个不同速度（或不同起点）游标的相对位置来编码全局信息——判环、找中点、定倒数第 k 都是同一招的变体。识别信号：判重复/判循环/找周期 + O(1) 空间；序列由"下一个"函数生成（链表 next、数组 nums[i]、数位平方和）都适用。关联：↔ LC142 环形链表II（进一步求环入口）、↔ LC287 寻找重复数（数组当隐式链表判环）、↔ LC234 回文链表（快慢指针找中点）。

要完成的任务

给定链表头节点 head，若链表有环，返回从头出发第一次进入环的节点；无环返回 null。不得修改链表。

字段含义

pos 是尾节点所连接节点的 0-based 下标，-1 表示无环；它只描述测试数据，不作为函数参数。评测按返回的节点对象判断答案。

示例 1

示例 2

示例 3

约束与保证

• 节点数在 [0,10⁴] 内，-10⁵ ≤ Node.val ≤ 10⁵。
• pos 为 -1 或链表中的有效下标。
• 题目要求不修改链表；进阶目标是 O(1) 额外空间。

暴力起手：哈希集记录访问过的对象，第一个重复出现的对象就是入口——O(n) 时间但 O(n) 空间。费的根源同 LC141：为一个位置答案存下了全部足迹。

① 约束排除：进阶要 O(1) 空间，哈希出局；题面还写明不得修改链表，"改值做标记""逐个断链看断到哪"这类小聪明也被封死。剩下的只有 141 已经验证过的武器：快慢指针能在环内制造一个相遇点。问题变成——相遇点里藏着入口的什么信息？

② 把两个路程写成等式（本题核心，LC287 直接引用）：设 head 到入口距离 a、入口沿环到相遇点 M 距离 b、M 沿环回到入口距离 c（环长 L=b+c）。相遇一刻：slow 走了 a+b；fast 速度是它两倍，走了 2(a+b)；而 fast 的路线可以拆成"和 slow 相同的 a+b，再加在环里多绕的整数圈"，即 2(a+b)=a+b+n(b+c)（n≥1 是 fast 多绕的圈数）。两边消去 a+b：

a+b = n(b+c)　⟹　a = n(b+c) − b = (n−1)(b+c) + c

③ 把等式翻译成走路方案：a = (n−1)(b+c) + c 读出来是一句话：从相遇点 M 出发走 a 步 ＝ 先走 c 步回到入口，再绕整 (n−1) 圈——落点仍是入口。而从 head 出发走 a 步，按定义也到入口。所以让 entry 从 head、slow 留在 M，同速各走一步：走满 a 步时两者必然同站入口。且在此之前不会相等——a>0 时 entry 一直在环外的直线段上，slow 一直在环里，碰不到；第一次 entry is slow 就是入口。注意全程不需要知道 n 是几：多绕的 (n−1) 圈自动被"绕回原地"吸收。

④ 常见困惑——为什么偏偏是"再走 a 步"两边同时到？不是巧合，是把未知量 a 从等式里"走"出来：我们不知道 a 是多少，但等式保证"head 出发走 a 步"和"M 出发走 a 步"落点相同（都是入口）；同速前进就是在同步枚举步数，第一次相等即第一次同落点。这也解释了为什么留守方必须从 M 出发——换成任何别的点，等式就不成立了。

⑤ 用样例验证：1→2→3→4→5，5 指回 3：a=2（1→2→3 前两步）、入口=3。阶段一在 4 相遇（M=4），b=1（3→4）、c=2（4→5→3）、L=3；检验等式：slow 走 a+b=3 步，fast 走 6 步、多绕 n=1 圈，a = 1×3 − 1 = 2 ✓。阶段二：entry 走 1,2,3；slow 走 4,5,3——第 2 步同落 3，正是入口。

距离关系：head --a--> [入口X] --b--> [相遇点M]
                         ^                     |
                         +---------c-----------+   环长=b+c

具体链：1 -> 2 -> [3] -> 4 -> 5
                    ^              |
                    +--------------+   （5.next 回到同一个 3）

帧1  Floyd 起点：slow=1，fast=1
帧2  两轮后：slow=3，fast=5
帧3  第一次相遇：slow=fast=4（M）
帧4  entry 从 1、slow 从 4 同速走：1/4 → 2/5 → 3/3
帧5  同一对象 3，确定入口 ✓

本例 a=2；M=4 沿环到入口也走 4->5->3 共 2 步，
所以两指针恰好同步到 3。

验证 a=c:a=2(head→入口 3), c=2(相遇点 4 绕回入口:4→5→3), 恰好相等, 印证推导。

class Solution:
    def detectCycle(self, head):
        # 1. Floyd 第一阶段：寻找环内相遇点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                # 2. 一方从头、一方留在相遇点，同速走到入口
                entry = head
                while entry is not slow:
                    entry = entry.next
                    slow = slow.next
                return entry
        return None

时间 O(n)：找相遇 O(n)（slow 入环后不满一圈即被追上）+ 找入口再走 a<n 步；空间 O(1)。高频追问一："fast 多绕的圈数 n 到底是几，影响答案吗？"——不影响也不用算：(n−1) 圈在第二阶段表现为留守指针在入口"原地转整圈"，落点不变，这正是等式改写成 (n−1)(b+c)+c 的意义。追问二："为什么假设 slow 相遇前只走了 a+b、没多绕圈？"——slow 踏进入口时 fast 已在环内、间距至多 L−1，每轮缩 1，所以 slow 在环内走不满一圈（b<L）就被追上，路程恰是 a+b。

功能：环入口在中段返回该点；边界：无环返回 None、单结点自环入口=自身；特殊：入口即头结点（a=0，entry 与 slow 起点即相遇）。

考查 Floyd 第二阶段的数学推导。收束成通用范式：相遇点不是终点而是信息载体——用一条路程等式把未知距离转成"换起点、同速再走"的同步终点。识别信号：要找"循环开始的位置"且 O(1) 空间、不许改结构；把 next 换成 nums[i]，值域 [1,n] 数组必有环、环入口＝重复数，就是 LC287。关联：↔ LC141 环形链表（判环与相遇论证的基础）、↔ LC287 寻找重复数（本题 a=n(b+c)−b 推导的直接复用）。

要完成的任务

给定两个按非递减顺序排列的单链表 list1 与 list2，把两条链表的现有节点拼接成一条同样有序的链表，并返回合并后头节点。

输入与输出

数组分别展示两条链表从头到尾的节点值；输出数组展示返回头节点沿 next 可访问到的值。

示例 1

示例 2

示例 3

约束与保证

• 两条链表的节点数都在 [0,50] 内。
• -100 ≤ Node.val ≤ 100。
• list1 与 list2 都已按非递减顺序排列。

暴力起手：收集两链所有值、排序后重建，O((m+n)log(m+n)) 时间、O(m+n) 空间。慢的根源：排序是在反复"重新发现"一个输入早已白送的事实——两条链各自有序，意味着全局最小值永远只会是两个当前头之一；对着两个候选做全量排序，就是把已知信息扔掉重算。

① 关键转化——归并视角：结果链从小到大逐个"认领"节点：每一步的候选只有 l1、l2 的当前头（各自链里头就是最小），比一次、接一个、前移一格，一趟走完。这正是归并排序 merge 步的链表版——LC148 和 LC23 都在反复调用它。

② dummy 哨兵——守住"头会被换掉"的场景：结果链的第一个节点来自 l1 还是 l2，要比过才知道——头节点无法预先确定（可能被换掉）的场景，就立一个 dummy 当"第 0 个节点"。它让"接第一个节点"和"接第任意个节点"共用同一行 tail.next=…，免去"结果还是空链"的分支；最后 dummy.next 才是真头。这套讲法在 2/19/24/25/148 里原样复用。

③ 收尾一行为什么合法：循环退出时一方为空，另一方剩余段自身有序，且（由 tail 的不变量）所有剩余值 ≥ 已合并段末尾——整段挂上即是正确答案，不需要继续逐个比。tail.next = l1 or l2 恰好取非空的那条。

④ 常见困惑——接走 l1 的头，会不会改坏 l1 链的内部结构？不会。tail.next=l1 只改写 tail 的出边，被认领节点自己的 next 原封不动；而 l1=l1.next 在同一条语句里先读后赋，余链入口稳稳交接。整个算法不新建任何节点，只是重新分配"谁指向谁"。

⑤ 用样例走一遍：1a→2→4a 与 1b→3→4b：认领顺序 1a（<= 取 l1）、1b、2、3、4a；此时 l1 空，整段接上 l2 剩余的 4b，得 1,1,2,3,4,4。等值对 1a/1b 因 <= 保持 l1 优先的稳定顺序。

l1: 1a -> 3 -> None      l2: 2 -> None
结果：dummy -> None，tail=dummy

里程碑1  选择 1a：dummy->1a，l1 前移到 3
里程碑2  选择 2 时覆盖 1a 的旧边：
           dummy->1a->2，l1 仍指向 3（因此 3 没丢）
里程碑3  l2 耗尽：tail=2，剩余 l1=3
里程碑4  整段拼接：dummy->1a->2->3->None ✓

class Solution:
    def mergeTwoLists(self, l1, l2):
        # 1. 哨兵统一处理结果链的第一个结点
        dummy = tail = ListNode()

        # 2. 每轮接入两个当前头中的较小者
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next

        # 3. 一方耗尽后，另一方剩余段可整段接入
        tail.next = l1 or l2
        return dummy.next

时间 O(m+n)，每个结点接一次；空间 O(1)（复用原结点，不新建）。递归写法栈深 O(m+n)。高频追问一："递归版怎么写？"——merge(l1,l2) = 较小头 + merge(其余)，代码三五行，但栈深 O(m+n)，链长上万时选迭代。追问二："为什么比较用 <= 不用 <？"——输出值序列相同，但 <= 让等值元素保持 l1 优先的稳定性；它同时是 LC148 归并排序稳定性的来源，改成 < 后 148 就不再是稳定排序。

功能：交替合并；边界：一方为空返回另一方、两方都空返回 None；特殊：一方所有值都小于另一方（尾部整段拼接）、等值元素（<= 保证稳定）。

考查 dummy 哨兵与双指针归并，是归并排序的合并子过程。收束成通用范式：多路各自有序 → 每步只需在各路当前头之间比较；结果头未定 → 先立哨兵统一接入动作。识别信号：合并/交织两条已排序结构、题面强调"已按 xx 顺序排列"；路数升到 k 时比较结构升级为最小堆。关联：↔ LC23 合并K个升序链表（k 路推广：堆或分治）、↔ LC148 排序链表（把本题当合并步的归并排序）。

要完成的任务

两个非空链表分别以逆序数字表示两个非负整数：头节点是个位，每个节点保存一位。计算两数之和，并用同样的逆序链表返回。

输入与输出

l1、l2 中的每个值都是十进制数字。除数字 0 本身外，输入整数没有前导零；输出也按“个位在头”的方式解释。

示例 1

示例 2

示例 3

约束与保证

• 每条链表的节点数在 [1,100] 内。
• 0 ≤ Node.val ≤ 9。
• 题目保证链表表示的数没有前导零。

暴力起手：把两条链各还原成整数、相加、再拆回链表。Python 大整数不怕溢出，但其它语言 100 位数字直接爆 long；更重要的是它绕了远路——还原和拆解各要一趟，而"逆序存储"本身就是出题人递来的箭头。

① 读约束里的信号：为什么偏偏"个位在头"？因为手算竖式加法就是从个位开始、进位往高位传——逆序链表让"沿 next 遍历"与"从低位到高位"两个方向天然重合。顺着走一遍、边走边加，才是这道题设计好的解法路径（正序版 LC445 反而要先做反转或用栈）。

② 关键转化：问题退化成竖式加法模拟：每一位 本位和 = 两个当前位 + 进位，其中 digit = 和 % 10 留下、carry = 和 // 10 上交下一位。链表只是数位容器，核心状态只有一个标量 carry。

③ 循环条件从"还有什么活没干完"推出：没干完的来源恰有三个——l1 没走完、l2 没走完、最后一位加完还欠着进位。三者取并集就是 while l1 or l2 or carry。想验证第三项的必要性，拿 999+1：两链都耗尽时 carry=1，必须再造一位，否则千位蒸发。

④ 常见困惑——carry 会不会大于 1、要不要循环借位？不会。单个数位最大 9，9+9+1=19，divmod 后 carry 最多是 1；这也是"进位只用一个 0/1 标量"的底气。

⑤ 用样例验证收尾轮：l1=[5]、l2=[5]：第 1 轮 5+5+0=10 → digit=0、carry=1，两输入耗尽；第 2 轮仅由 carry 驱动，0+0+1=1 → 追加 1。结果 0→1，逆序读是 10 ✓。

输入：l1: 5 -> None    l2: 5 -> None
初始：dummy -> None，tail=dummy，carry=0

里程碑1  初始化：结果空，carry=0
里程碑2  5+5+0=10：追加 0，carry=1；两输入耗尽
里程碑3  carry 单独触发下一轮：0+0+1=1
里程碑4  追加 1：dummy->0->1，carry=0，结束 ✓
结果 0->1 以逆序表示整数 10。

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = tail = ListNode()
        carry = 0

        # 1. 输入或末尾进位尚未耗尽，就继续处理一位
        while l1 or l2 or carry:
            digit_a = l1.val if l1 else 0
            digit_b = l2.val if l2 else 0

            # 2. 商是下一位进位，余数是当前结果位
            carry, digit = divmod(digit_a + digit_b + carry, 10)
            tail.next = ListNode(digit)
            tail = tail.next

            # 3. 较短链耗尽后保持 None，后续按 0 参与
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

时间 O(max(m,n))，逐位处理；空间 O(max(m,n)) 存结果链表（进位可能多一位），不计输出则只有 carry 等常数个变量。高频追问一："如果数字是正序存储（LC445）怎么办？"——加法只能从低位开始，先反转两链（或各压一个栈）再套本题模板，算完按需反转回去。追问二："能不能不建新链、原地复用较长链的节点？"——可以，把结果写回较长链并在必要时借用短链节点，额外空间降为 O(1)；但末位进位仍可能新建 1 个节点，且会破坏输入，面试要先声明。

功能：342+465=807；边界：一方明显更长（9->9 + 1）、其中一方为 0；特殊：最高位进位（5+5=10 → 0->1），全靠 carry 留在循环条件里。

考查进位处理与 carry 收尾。收束成通用范式：逐位/逐项模拟 + 一个标量携带跨轮状态（进位）；循环条件 = 所有"未完成来源"的并集。识别信号：数字以序列形式存储做算术（加法/加一/乘法）、低位对齐先处理——先问"进位状态是什么、何时清零"。关联：LC445 两数相加II（正序存储，先反转或用栈）、↔ LC21 合并两个有序链表（同款 dummy+tail 产出新链）、↔ LC19 删除倒数第N（同用 dummy 哨兵）。

要完成的任务

给定单链表头节点 head 和整数 n，删除倒数第 n 个节点，并返回删除后的头节点。

输入与输出

n=1 表示删除尾节点，n 等于链表长度时表示删除头节点；题目保证 n 有效。

示例 1

示例 2

示例 3

约束与保证

• 链表节点数 sz 满足 1 ≤ sz ≤ 30。
• 0 ≤ Node.val ≤ 100，且 1 ≤ n ≤ sz。
• 进阶要求只扫描链表一次。

暴力起手（两趟）：第一趟数出长度 L，第二趟走 L−n 步停在待删节点的前驱，改一条边跳过它。复杂度也是 O(L)，慢的不是量级而是趟数——"倒数第 n"依赖总长 L，看起来必须先数一遍。进阶要求一趟扫完：得在不知道 L 的情况下判断"距尾还有多远"。

① 关键转化——把"与尾的距离"翻译成"与同伴的距离"：单链表只能向前，无法从尾往回退；但"倒数第 n"本质是一个相对位置。让 fast 先走若干步、再与 slow 同速前进：同速移动中两者间距永远不变，于是"fast 撞到尾后的 None"那一刻，slow 距离链尾的步数恰好等于出发时的领先量——尾部信息被间距编码，一趟搞定。这是快慢指针家族里"固定间距"的用法（LC141 是"不同速度"的用法）。

② dummy 哨兵——守住"头会被换掉"的场景：删除动作发生在前驱身上，而头节点没有前驱，且 n=L 时被删的正是头。统一讲法：头节点可能被换掉的场景，就挂一个 dummy 当人造前驱，让"删头"和"删中间"共用同一行 slow.next = slow.next.next，最后返回 dummy.next。

③ 先行步数 n+1 从目标倒推：从 dummy 起给位置编号 0…L，fast 走到 None 相当于站上位置 L+1。此刻 slow 位置 = L+1−(先行步数 k)；我们要它停在待删节点（倒数第 n＝位置 L−n+1）的前驱，即位置 L−n。解 L+1−k = L−n 得 k = n+1。直觉版：想停在"目标前一格"，就要比 n 多领先一格。

④ 常见困惑——网上有的版本 fast 先走 n 步，谁对？都对，口径不同：先走 n 步的版本配的是"同步到 fast.next 为 None（fast 停在尾节点）就停"，slow 同样落在前驱。错的是混搭：先走 n 步却同步到 fast=None，slow 就会停在待删节点本身。选定一套口径背到底：都从 dummy 出发、先行 n+1、走到 fast=None。

⑤ 用样例走一遍：dummy→1→2→3→4、n=2（删 3）：fast 先行 3 步到节点 3；同步两轮：fast 4→None，slow 1→2。slow=2 正是 3 的前驱，2.next=4 后主链 1→2→4 ✓（与图解帧一致）。

例：dummy -> 1 -> 2 -> 3 -> 4 -> None，n=2（删结点 3）

里程碑1  fast=slow=dummy
里程碑2  fast 先走 n+1=3 步：
      dummy -> 1 -> 2 -> 3 -> 4 -> None
        slow              fast
里程碑3  同步两轮后：slow=2，fast=None；slow 是 3 的前驱
      dummy -> 1 -> 2 -> 3 -> 4
                         ^
                        slow.next
里程碑4  写 slow.next=slow.next.next 后：
主链：dummy -> 1 -> 2 ----------> 4 -> None
脱链：                    3 ------> 4
                          （3 仍指 4，但已无主链前驱）

class Solution:
    def removeNthFromEnd(self, head, n):
        # 1. 哨兵为头结点提供统一前驱
        dummy = ListNode(0, head)
        fast = slow = dummy

        # 2. fast 先走 n+1 步，让 slow 最终停在待删结点前驱
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            fast, slow = fast.next, slow.next

        # 3. 前驱越过目标结点
        slow.next = slow.next.next
        return dummy.next

时间 O(L) 一趟；空间 O(1)。高频追问一："两趟法也是 O(L)，一趟法真正的优势在哪？"——量级相同；优势在数据只能顺序读一遍的场景（流式输入、磁盘顺序读），以及常数上少扫一遍。面试把两法都摆出来讲清 trade-off 比只写一趟法更加分。追问二："如果题目不保证 n 合法怎么办？"——先行阶段里 fast 提前变 None 就说明 n > L，此时可直接返回原链或报错，一行判断即可兜底。

功能：删中间结点；边界：删头结点（n=L，靠 dummy）、删尾结点（n=1）；特殊：链表仅一个结点且 n=1（返回 None）。

考查快慢指针固定间距 + dummy 处理删头。收束成通用范式："与尾部的相对位置"→ 固定间距双指针，让先行者撞尾时后行者恰好到位；要动手的位置在前驱 → 立 dummy 守住换头场景。识别信号：倒数第 k / 后半段 / 距尾多远 + 单链表 + 一趟扫描。关联：LC876 链表中间结点（间距换成"速度差"的变体）、↔ LC141 环形链表（快慢指针族）、↔ LC21 合并两个有序链表（dummy 哨兵同款讲法）。

要完成的任务

给定单链表头节点 head，每两个相邻节点交换一次，并返回交换后的头节点。只能改变节点之间的连接，不能只交换节点值。

输入与输出

数组按 next 顺序展示链表。若最后只剩一个节点，它没有配对对象，应原样留在尾部。

示例 1

示例 2

示例 3

示例 4

约束与保证

• 节点数在 [0,100] 内。
• 0 ≤ Node.val ≤ 100。
• 不得通过修改节点值完成交换。

一句话总纲：立 dummy 当第 0 个节点；只要前驱后面还够两个节点，就取出这相邻一对，按固定的三笔改线完成交换，再把前驱移到这一对交换后的新尾；剩下不足两个时停止，返回 dummy.next。

① 暴力起手 + 约束排除：最省事的写法是隔一个换一次节点值——题目明文禁止，出题人要考的恰是指针重接本身；新建一条链按 2,1,4,3 的顺序抄一遍则费 O(n) 空间。两条捷径都被堵死，只剩原地改边。

② 关键转化——整链＝一串相邻对：每对内部做一次"最小号的 LC206 反转"（段里只有两个节点），对与对之间靠一个前驱指针传递衔接。这正是 LC25 取 k=2 的特例：探测（还剩两个吗）→ 段内反转 → 缝合前驱。

③ dummy 哨兵——守住"头会被换掉"的场景：第一对交换后，新头是原来的第二个节点——头被换掉了。统一讲法：立 dummy 当第 0 个节点，让第一对和后面每一对都有现成前驱，返回 dummy.next。

④ 三笔改线的顺序从"先断哪条会丢什么"推出：一对交换要写三条边：first.next、second.next、pair_prev.next。三条旧边里，唯一没有备份、写丢就找不回的信息是 second.next（后段入口）。

第一笔 first.next = second.next：趁后段入口还在，先把后段挂到 first 身上。
第二笔 second.next = first：对内掉头。若把这笔提前到第一笔之前，后段入口先被覆盖，first 只能指向 second 自己——自环（坑①）。
第三笔 pair_prev.next = second：把新对头接回主链。它不覆盖任何还需要的信息，放最后最清晰。

⑤ 常见困惑——pair_prev 该前移到 first 还是 second？交换后本对顺序是 second→first，对尾是 first，所以 pair_prev = first。凭"变量名叫 first 就该在前"的直觉移到 second，下一对会从错位的地方取节点（见坑②的反例）。

⑥ 用原题示例 1 走一遍：dummy→1→2→3→4。

第一对：first=1、second=2。
第一笔 1.next=3：后段 3→4 挂到 1 身上，保住不丢。
第二笔 2.next=1：对内掉头。
第三笔 dummy.next=2：现场稳定为 dummy→2→1→3→4。
pair_prev 前移到对尾 1，正好是下一对 (3,4) 的前驱 ✓。
第二对同法得 dummy→2→1→4→3；再往后不足一对，返回 [2,1,4,3] ✓。

⑦ 解法②（递归）：信任 swapPairs(second.next) 已把后段交换完并返回其新头。本层只做两笔：first.next=递归结果（对应迭代的"保后段"）、second.next=first（对内掉头），返回 second——"接回前驱"由上一层的这条赋值隐式完成。不足两个节点的尾段原样返回即递归出口。迭代 O(1) 空间为首选，递归胜在结构直白。

解法① 迭代，交换第一对 1(a)、2(b)
帧1  dummy -> 1(a) -> 2(b) -> 3 -> 4，pre=dummy

写 a.next=b.next 后（a 越过 b；3 暂被 a、b 双重指向）：
      dummy -> 1(a) ---------> 3 -> 4
                     2(b) ----^
                     （b 变量保住脱离主路径的结点 2）

写 b.next=a 后（交换对已成形，但尚未接回 pre）：
      b 路径：2 -> 1 -> 3 -> 4
      主路径：dummy -> 1 -> 3 -> 4
      结点 1 此刻有 dummy 与 b 两个前驱引用

写 pre.next=b 后（稳定态）：
帧4  dummy -> 2 -> 1 -> 3 -> 4，pre 前移到 1

帧5  第二对同法稳定：dummy -> 2 -> 1 -> 4 -> 3 -> None

解法② 递归回溯
帧1  递归先稳定后段：4 -> 3 -> None
帧2  回到首对：1.next=4，再令 2.next=1
帧3  最终：2 -> 1 -> 4 -> 3 -> None