Hot100 归纳与题型对比

使用说明¶

这份 notebook 是基于你当前 docs/notebooks 目录里已经写出的 hot100 题解整理出来的复习稿，重点不是把题目重新抄一遍，而是把你已经写过的解法抽象成可复用的模板。复习时建议按下面的顺序看：先判断题目属于哪一类，再回忆该类题的“状态 / 指针 / 数据结构”如何设计，最后再看和相似题的区别。这样做的目的，是让你以后做新题时不靠题感，而是靠模板匹配和约束分析来落地。

当前仓库里 11.回溯.ipynb、12.贪心算法.ipynb、13.图论.ipynb、14.二分查找.ipynb 内容基本为空或未整理，这份笔记只对现有有效代码进行总结。

hot100 的主线¶

当前的题解结构，已经自然形成了几条主线：

1. 哈希 / 前缀和 / 集合判重：本质是在问“我之前见过什么”“某种状态出现过几次”。
2. 双指针 / 滑动窗口 / 单调队列：本质是在问“区间如何在线维护”。
3. 动态规划：本质是在问“当前答案能否由更小子问题转移而来”。
4. 链表 / 二叉树：本质是在问“指针或递归返回值该表达什么”。
5. 栈 / 单调栈 / 堆：本质是在问“局部最优结构如何持续维护”。
6. 矩阵 / 排序：本质是在问“原地修改的顺序”和“分治边界”是否清晰。

真正复习时，不要先背题号，而要先问自己：

• 这题是不是在找配对、判重、计数？如果是，先想哈希。
• 这题是不是在维护一个连续区间？如果是，先想双指针 / 滑动窗口。
• 这题是不是要求最优值、方案数、可行性？如果是，先想 DP。
• 这题是不是一边遍历一边维护“最近更大/更小”或“前 k 大/中位数”？如果是，先想栈或堆。
• 这题是不是树上“路径、深度、祖先、构造、遍历”问题？如果是，先确定递归函数含义。

总览表：题型 -> 模板 -> 区别点¶

题型	代表题	统一模板	你这套代码里的关键动作	最容易混淆的点
哈希判重 / 配对	两数之和、字母异位词分组、最长连续序列	dict/set 存状态	边遍历边查补数、按特征分组、只从序列起点开始扩展	set 适合判存在，dict 适合计数/映射
前缀和 + 哈希	和为 K 的子数组、路径总和 III	记录“前缀和出现次数”	查 current - target 出现了几次	不是找一个区间，而是统计所有以当前位置结尾的合法区间
双指针同向	移动零、删除倒数第 N 个节点、无重复子串	快慢指针 / 左右边界同向推进	一个指针扫数据，一个指针维护有效区	是否允许收缩、何时更新答案
双指针对撞	盛最多水的容器、接雨水、回文链表	左右向中间逼近	始终移动更可能改进答案的一侧	为什么移动短板、为什么“谁小算谁”
滑动窗口	最小覆盖子串、找到异位词、无重复最长子串	右扩张、左收缩、维护窗口合法性	计数器 / 集合 / 满足条件数量	什么时候窗口“合法”，什么时候要一直收缩
单调队列	滑动窗口最大值	队列里存下标，值单调	入队前清理尾部，出队时移除过期下标	存的是下标不是值，因为要判断是否过期
一维 DP	爬楼梯、打家劫舍、零钱兑换、单词拆分	dp[i] 表示前 i 项或以 i 结尾的答案	枚举转移来源，初始化边界	dp 含义不清就会写乱
二维 DP	不同路径、最小路径和、LCS、编辑距离、最长回文子串	dp[i][j] 表示两个维度上的子问题	从更小矩形转到更大矩形	下标语义：[:i] 还是到 i 为止
链表指针操作	反转链表、K 个一组翻转、合并 K 链表、LRU	dummy + 局部断链 + 重新连接	先保住后继，再改指针，再接回主链	断链和回接顺序错了最容易挂
二叉树递归	最大深度、直径、最大路径和、最近公共祖先	设计递归函数返回值	返回“高度 / 增益 / 是否找到 / 构造后的子树”	递归返回值和全局答案经常不是同一个东西
层序 / BFS	层序遍历、右视图	队列按层处理	每层固定长度遍历	什么时候记录每层第一个或最后一个元素
BST 专题	验证 BST、第 K 小、有序数组转 BST	利用中序有序性	中序遍历、左右边界递归建树	BST 不是普通树，能用“有序”信息剪枝
单调栈	每日温度、柱状图最大矩形、有效括号（广义栈）	维护“还没结算”的状态	遇到更大/更小元素时结算栈顶	想清楚栈里存下标还是字符
堆	第 K 大、前 K 高频、数据流中位数	维护一个局部最优集合	小根堆保留 top k，双堆维护中位数	堆不负责整体排序，只负责堆顶最值
矩阵原地操作	矩阵置零、旋转图像、螺旋矩阵	分层 / 标记 / 行列映射	先标记后修改、先转置后翻转	原地题最怕覆盖掉还要用的信息
排序与分治	快排、归并、排序链表	先分，再合 / 划分	partition 或 merge 的边界控制	快排偏“划分”，归并偏“稳定合并”

1. 哈希、集合、前缀和：先问“历史信息是否有用”¶

核心套路¶

你在哈希专题和部分字符串 / 树题里，最稳定的思路就是：一边扫当前元素，一边查询过去出现过的状态。像“两数之和”是查补数是否出现；“字母异位词分组”是把同类对象映射到同一个 key；“最长连续序列”是把数组变成集合后，只从一个连续段的起点开始扩展，避免重复遍历；“和为 K 的子数组”和“路径总和 III”则进一步升级成“前缀和计数”，即不再问一个值是否出现过，而是问某个前缀状态出现过多少次。这个模板一旦吃透，数组问题和树路径问题会被统一成同一个模型。

对比记忆¶

题目	本质问题	核心状态	为什么这样做
两数之和	找配对	target - x 是否出现	每扫到一个数，就立刻知道它的搭档是谁
字母异位词分组	找同类	排序后字符串 / 26 频次数组	同一类必须映射到同一个规范 key
最长连续序列	找连续段长度	set + 只从起点扩展	避免每个元素都重复向后扫
和为 K 的子数组	统计区间个数	prefix_count[presum]	区间和 = 两个前缀和之差
路径总和 III	统计树上向下路径个数	DFS 路径前缀和计数	本质就是树上的“和为 K 的子数组”

区别点¶

“哈希表”最容易学会，却也最容易只学到表面。真正的分界线在于：如果只关心“存不存在”，set 足够；如果关心“这个状态对应什么”或“出现多少次”，必须用 dict。而前缀和题再进一步，不是在记数字本身，而是在记“走到当前位置之前的累积状态”。这就是为什么 560 和 437 看起来一个是数组、一个是树，但核心解法几乎同构。

2. 数组、双指针、滑动窗口：先问“区间是否连续”¶

核心套路¶

你在数组和双指针部分已经覆盖了三种非常典型的连续结构题：第一类是快慢指针重写数组，比如“移动零”“旋转数组”“合并区间”这类题，本质是维护一个已经处理好的前缀；第二类是左右指针对撞，如“盛最多水的容器”“接雨水”，核心不是穷举，而是利用边界约束决定该移动哪一侧；第三类是滑动窗口，如“无重复字符的最长子串”“最小覆盖子串”“找到异位词”，本质是维护一个始终可增可缩的合法区间。你这套代码的共同优点，是都把“什么时候扩、什么时候缩、什么时候结算答案”写得很明确。

对比记忆¶

题目	模板	关键不变量	复习时先想什么
移动零	同向双指针	[0, write) 都是处理好的非零区	write 指向下一个该放非零的位置
盛最多水的容器	对撞双指针	面积由短板决定	为什么必须移动短板
三数之和	排序 + 固定一个数 + 左右夹逼	去重后枚举	先排序才能双指针去重
接雨水	对撞双指针	谁的边界更小，谁先结算	min(l_max, r_max) 决定水位
无重复最长子串	滑动窗口	窗口内无重复	重复出现后要持续缩窗
最小覆盖子串	滑动窗口 + 计数	窗口已覆盖全部需求字符	合法后尽量缩到最短
找到异位词	固定长度窗口	窗口字符频次与目标一致	重点在“窗口长度固定”
滑动窗口最大值	单调队列	队头永远是当前窗口最大值下标	队列里存下标而不是值

区别点¶

很多人会把双指针和滑动窗口混成一个东西，但你复习时必须区分清楚：双指针更像是利用单调性做决策，滑动窗口更像是在维护一个连续合法区间。例如“盛水最多的容器”不能缩完再扩，因为答案依赖两端边界；而“最小覆盖子串”必须右扩找可行解、左缩找更优解。至于“滑动窗口最大值”，虽然也有窗口，但真正决定复杂度的是单调队列，不是简单的左右边界。

3. 动态规划：先把 dp 含义说清楚，再写转移¶

核心套路¶

你现在的动态规划代码已经把 hot100 里最常见的两条线都覆盖了：一维 DP 和二维 DP。一维 DP 里，dp[i] 往往表示“前 i 个位置的最优解”或者“以 i 结尾的最优解”，代表题有“爬楼梯”“打家劫舍”“零钱兑换”“单词拆分”“最长递增子序列”“乘积最大子数组”“分割等和子集”“最长有效括号”；二维 DP 则是“不同路径”“最小路径和”“最长公共子序列”“编辑距离”“最长回文子串”。你写法里最大的优点是，很多题已经显式写出 dp[j] / dp[i][j] 的含义，这正是 DP 最重要的第一步。

一维 DP 对比¶

题目	dp 定义	转移核心	关键区别
爬楼梯	到第 i 阶的方法数	dp[i]=dp[i-1]+dp[i-2]	标准线性递推
打家劫舍	前 i 家可偷到的最大值	偷或不偷当前家	典型“相邻约束”
完全平方数 / 零钱兑换	凑成 i 的最优值	枚举一个可选物品再转移	完全背包味道很重
单词拆分	前 i 个字符能否拆开	枚举切分点 j	可行性 DP
LIS	以 i 结尾的最长递增长度	枚举前面比它小的 j	状态依赖“以谁结尾”
乘积最大子数组	以 i 结尾的最大/最小乘积	同时维护 max/min	负数会让大小关系翻转
分割等和子集	容量为 j 是否可达	0-1 背包倒序更新	优化目标是“能否装满”
最长有效括号	以 i 结尾的最长合法长度	看前一个字符和可拼接长度	本质是结构拼接

二维 DP 对比¶

题目	dp[i][j] 定义	转移核心	关键区别
不同路径	走到 (i,j) 的方案数	上方 + 左方	求方案数
最小路径和	走到 (i,j) 的最小代价	min(上,左)+当前值	求最优值
最长回文子串	子串 s[i:j] 是否回文 / 最优长度	看两端是否相等以及内部状态	区间 DP
LCS	text1[:i] 和 text2[:j] 的最长公共子序列长度	相等取左上+1，否则取左/上最大	双序列对齐
编辑距离	word1[:i] 到 word2[:j] 的最少操作数	插入、删除、替换三选一	多操作最小代价

区别点¶

DP 最常见的错误不是不会写，而是状态定义模糊。一旦 dp 的含义不清，初始化、遍历顺序、转移来源全会错。你复习时强制自己先回答三句话：dp 表示什么、从哪里转移、初始边界是什么。只要这三句说清，很多题代码都能自然长出来。

4. 链表：所有高频题几乎都绕不开 dummy、断链、回接¶

核心套路¶

你链表专题写得比较完整，已经把 hot100 里最典型的指针操作都覆盖到了：相交链表、反转链表、回文链表、环形链表 I/II、合并两个有序链表、两数相加、删除倒数第 N 个节点、两两交换、K 个一组翻转、随机链表复制、排序链表、合并 K 个升序链表、LRU。虽然题面看起来五花八门，但核心操作其实高度统一：先定位边界，再暂存后继，再原地改指针，最后把局部结果重新接回主链。只要这四步顺序不乱，链表题就会稳很多。

对比记忆¶

题目	核心技巧	为什么重要
反转链表	pre / cur / nxt 三指针	链表反转的基础母题
回文链表	快慢指针找中点 + 反转后半段	把链表题转成数组回文比较
环形链表 I/II	Floyd 快慢指针	一个判有环，一个求入环点
删除倒数第 N 个节点	dummy + 快慢指针间隔 N	删除头节点时也统一处理
两两交换 / K 个一组翻转	分组反转 + 回接	局部操作后必须接回原链
合并两个 / K 个有序链表	拉链法 / 分治两两合并	合并 K 条时本质是归并思想
随机链表复制	原节点与拷贝节点映射	哈希表保存“原 -> 新”关系
排序链表	快慢指针切分 + 归并	链表适合归并，不适合随机访问
LRU	哈希表 + 双向链表	O(1) 查询 + O(1) 移动最近使用节点

区别点¶

链表题最大的难点不是思路，而是实现顺序。比如 25. K 个一组翻转，你代码里先统计总长度，再每 k 个做一次局部反转，最后用 trail 和 p0 接回整条链，这个顺序非常标准；23. 合并 K 个升序链表 则不是暴力一个个接，而是按分治思路两两合并，本质和归并排序一致。复习时你可以把链表题统一看成“局部子链表加工题”，这样不会被题目外观带偏。

5. 二叉树：先定义递归函数的返回值，再决定是否需要全局变量¶

核心套路¶

你二叉树 notebook 的覆盖面很完整，包含遍历、层序、BST、构造、路径、祖先和树形 DP。复习树题时，最重要的不是一上来写代码，而是先问：递归函数到底要返回什么信息给父节点。有些题返回“高度”，比如最大深度；有些题返回“单边最大贡献”，比如最大路径和；有些题返回“某个子树构造后的根节点”，比如由前序和中序构造二叉树；有些题其实主要答案不在返回值里，而在全局变量里，比如直径、最大路径和、路径总和 III。你现在的代码已经体现出这个区分，这是树题复习的关键。

对比记忆¶

模板	代表题	递归函数返回什么	全局变量是否常见
基础 DFS 遍历	前中后序、最大深度、翻转二叉树	遍历结果 / 高度 / 新子树根	视题目而定
对称 / 相同结构判断	对称二叉树	两棵子树是否镜像	不需要
树形 DP	二叉树直径、最大路径和	高度 / 单边贡献	常需要全局最优
层序 BFS	层序遍历、右视图	不靠递归，靠队列按层处理	不需要
BST 有序性	验证 BST、第 K 小	中序序列特征	可能用中序计数
构造类	有序数组转 BST、前序中序建树	构造后的根节点	不需要
路径计数	路径总和 III	当前前缀和 DFS	需要路径计数结构
祖先问题	最近公共祖先	在子树中是否找到目标节点	不一定要全局变量

重点区别¶

• 104. 最大深度：递归返回高度，父节点只需要 max(left, right) + 1。
• 543. 二叉树的直径：递归仍返回高度，但真正答案是 left_height + right_height 的最大值，所以要额外维护全局最优。
• 124. 二叉树最大路径和：和直径很像，但返回给父节点的只能是一条单边路径贡献，左右两边同时向上会断结构；而全局答案可以考虑 left_gain + node.val + right_gain。
• 437. 路径总和 III：不是传统“从根到底”的树路径题，而是树上的前缀和计数，和 560. 和为 K 的子数组 是同模板。
• 98. 验证 BST 与 230. 第 K 小元素：都利用 BST 的中序有序性，这类题一旦识别出是 BST，就优先想中序，不要按普通树硬做。

6. 栈、单调栈、堆：维护一个“暂时还不能结算”的结构¶

核心套路¶

栈和堆题的共性，是都在维护一个局部结构，但用途不同。栈更强调“后进先出”的匹配关系，或者维护一个等待未来信息来结算的序列；单调栈则是让这个等待序列带有单调性，以便一旦遇到更大/更小元素就能批量结算；堆强调的是动态维护最值，不在乎整体顺序。你现有代码里的“有效括号”“字符串解码”“每日温度”“柱状图最大矩形”“数组中的第 K 个最大元素”“前 K 个高频元素”“数据流中位数”就是三类典型代表。

对比记忆¶

题目	数据结构	维护对象	为什么它有效
有效括号	普通栈	还没匹配的左括号	遇到右括号时只和最近左括号配对
字符串解码	栈	进入 [ 前的字符串和重复次数	出栈时恢复上一层上下文
每日温度	单调递减栈	还没找到更高温的下标	一旦遇到更高温就能结算若干天
柱状图最大矩形	单调递增栈	以某柱高为最短板时的最大宽度	出栈时左右边界同时确定
第 K 个最大元素	小根堆 / 快速选择	当前 top k	只保留必要候选
前 K 个高频元素	小根堆	频率 top k	堆顶永远是当前最弱候选
数据流中位数	双堆	较小一半和较大一半	中位数只取决于中间边界，不取决于全排序

区别点¶

复习时一定记住一句话：栈解决“最近相关”，堆解决“全局局部最值”。比如“每日温度”关心的是每一天后面最近一个更高温度，所以用单调栈；“数据流中位数”关心的是动态集合中间位置，所以用双堆把数据分成两半。你 295 的写法里先入左堆、再把左堆最大值送到右堆、最后重新平衡，这个流程就是标准模板，后续遇到“动态第 k 大 / 中位数 / top k”都可以直接套。

7. 矩阵、排序、数组原地题：先保住信息，再做覆盖¶

核心套路¶

矩阵和排序题看起来比较分散，但你当前代码体现出的共同点非常明确：原地修改题最重要的是操作顺序，分治排序题最重要的是边界和合并逻辑。矩阵置零要先记录哪些行列需要清零，否则你会把原始信息提前污染；旋转图像一般拆成“转置 + 每行翻转”；螺旋矩阵则是按上右下左四条边分层遍历。排序部分则分成两大套路：快速排序强调 partition，归并排序强调把两个有序段合并成一个有序段，链表排序也因此天然适合归并。

对比记忆¶

题目	核心动作	区别点
矩阵置零	先标记后清零	不能一看到 0 就立即扩散修改
螺旋矩阵	按边界分层遍历	注意缩边界和终止条件
旋转图像	转置 + 翻转	原地旋转通常靠坐标映射完成
合并区间	先按左端点排序再扫描合并	当前区间能否与结果尾部合并
快速排序	划分 + 递归处理两侧	重点是 pivot 和 partition 正确性
归并排序	递归切分 + merge 合并	重点是 merge 的双指针
排序链表	快慢指针切半 + 链表 merge	链表没有随机访问，更适合归并

区别点¶

数组原地题最容易犯的错，是“边修改边丢信息”；排序题最容易犯的错，是“分治边界不清”。所以这类题你复习时应该先检查自己有没有回答两个问题：第一，后面还要不要用到现在的原始值；第二，当前递归 / 循环处理的闭区间到底是什么。

8. 一组高频易混题对照¶

题目 A	题目 B	相同点	真正区别
和为 K 的子数组	路径总和 III	都是前缀和 + 哈希计数	一个在线性数组上，一个在 DFS 路径上，树题多一步回溯恢复现场
无重复最长子串	最小覆盖子串	都是滑动窗口	前者维护“无重复”，后者维护“覆盖完成”，合法条件完全不同
滑动窗口最大值	每日温度	都有“单调”味道	前者是单调队列维护当前窗口最值，后者是单调栈等待未来结算
二叉树直径	二叉树最大路径和	都是树形 DP	直径统计边数/高度组合，最大路径和统计节点值增益，负贡献要截断
反转链表	K 个一组翻转	都是局部指针反转	后者多了“分组边界”和“反转后接回原链”
合并两个有序链表	合并 K 个有序链表	都是链表拉链法	K 个要么分治、要么堆优化，不能简单线性串着合
第 K 个最大元素	前 K 个高频元素	都可用堆保留 top k	一个按数值比较，一个按频率比较
最大子数组和	乘积最大子数组	都是以当前位置结尾的 DP	乘积题因负数存在必须同时维护最大和最小
不同路径	最小路径和	都是网格 DP	一个求方案数，一个求最优代价，转移形式相似但语义不同
验证 BST	第 K 小元素	都利用 BST 中序有序	一个验证整体有序约束，一个利用有序序列做计数定位

9. 复习建议：把题目压缩成“识别信号”¶

如果你后续要继续刷题，我建议你不要再按题号记忆，而是把每类题压缩成几个识别信号：

• 看到“配对、判重、分组、出现次数”就优先想哈希。
• 看到“连续区间、最长/最短子串、覆盖、异位词”就优先想滑动窗口。
• 看到“左边界 / 右边界 / 短板 / 接水 / 回文”就优先想对撞双指针。
• 看到“方案数、最大值、最小值、能不能凑出来”就优先想 DP。
• 看到“树上路径、祖先、深度、构造”就先定义递归函数意义。
• 看到“最近更大 / 最近更小 / 等待未来结算”就优先想单调栈。
• 看到“前 k、大顶/小顶、中位数、数据流”就优先想堆。
• 看到“原地矩阵修改、旋转、置零”就先想如何避免信息被覆盖。

真正拉开差距的，不是你会不会背出某一题，而是你能不能在 30 秒内把新题归到正确模板里。你这套 hot100 代码已经把主干模板搭起来了，接下来训练重点应该是：拿一道新题时，先说出它属于哪一类、状态怎么定义、为什么不用别的模板。

10. 当前仓库中尚未成型的专题¶

当前目录里以下 notebook 还没有形成可复习的稳定代码模板：

• 11.回溯.ipynb
• 12.贪心算法.ipynb
• 13.图论.ipynb
• 14.二分查找.ipynb

建议你后续补这四类时，也沿用这份笔记的整理方式：

• 回溯：重点整理“路径、选择列表、结束条件、去重方式”。
• 贪心：重点整理“局部最优为什么能推出全局最优”。
• 图论：重点整理“DFS / BFS / 入度拓扑 / 并查集”各自的题型信号。
• 二分查找：重点整理“查值、查边界、答案二分”三个层次。