LeetCode 热题 100

LeetCode 官方学习计划「热题 100」¹的题解，一题一篇，分组沿用官方的 15 个题型。题单 2026-09-29 抓取，存档在 assets/hot100.json。

每篇骨架是题 → 一句话 → 关键技巧 → 解 → 延伸，价值密度在"关键技巧"——为什么想得到、为什么是对的。题意用自己的话概括，原文点每篇顶部的 LeetCode 链接看。

「解」是能直接贴进 LeetCode 提交的 Python3 class Solution，页尾「自测」折叠块是断言。仓库里的 scripts/check-leetcode.py 把每篇的 python 块拼起来、垫上 LeetCode 同款预置环境（ListNode、TreeNode、常用 import）真跑一遍——断言过不了的题解不进库。

哈希

1. 两数之和 · 简单 —— 边扫边查「补数见过没」，一遍哈希 O(n)；先查后存，天然避开同一元素用两次
49. 字母异位词分组 · 中等 —— 给「等价类」造一个规范形当哈希键——排序串或 26 维计数元组，同类必同键、异类必异键
128. 最长连续序列 · 中等 —— 只从「序列起点」（x-1 不在集合里）往后数，每个数至多被走两次，不排序也能 O(n)

双指针

283. 移动零 · 简单 —— 快慢指针原地「压缩」：慢指针左边永远是已处理好的非零前缀，交换一趟即稳定分区
11. 盛最多水的容器 · 中等 —— 双指针从两端收缩，每次挪矮的那边——矮边在当前宽度下已取到最优，丢掉它不会错过答案
15. 三数之和 · 中等 —— 排序后固定一个数、剩下跑有序两数之和；去重靠「同值只当一次代表」，不靠 set
42. 接雨水 · 困难 —— 每格水位 = min(左最高, 右最高) − 自身；双指针让矮的一侧先结算，O(1) 空间拿到那个 min

滑动窗口

3. 无重复字符的最长子串 · 中等 —— 可变长滑动窗口的母题：右端贪心扩、违规就收左端；记下标可让左端直接跳，不必一步步挪
438. 找到字符串中所有字母异位词 · 中等 —— 定长滑动窗口 + 计数差：进一个出一个只改两格，用「不匹配字母数」O(1) 判等，不必每步比 26 格

子串

560. 和为 K 的子数组 · 中等 —— 子数组和 = 两个前缀和之差；边扫边查「前缀 s−k 出现过几次」，有负数时滑窗失效就靠它
239. 滑动窗口最大值 · 困难 —— 单调队列：新来的更大就把队尾「永无出头之日」的旧元素踢掉，队头即窗口最大，均摊 O(1)
76. 最小覆盖子串 · 困难 —— 求最短合法窗口：右端扩到刚好覆盖，再尽量收左端；用「还缺几个字符」一个整数 O(1) 判覆盖

普通数组

53. 最大子数组和 · 中等 —— Kadane：以 i 结尾的最优只有「接上前面」或「另起炉灶」两种，前面的累计和为负就扔——一维 DP 压成一个变量
56. 合并区间 · 中等 —— 区间题先按左端点排序，之后只需和「结果里最后一个区间」比——能否重叠只看它的右端点
189. 轮转数组 · 中等 —— 三次翻转实现原地轮转：(AB)ᴿ = BᴿAᴿ，整体反转后两段各自翻回就是 BA，O(1) 空间
238. 除了自身以外数组的乘积 · 中等 —— 「除自己以外」= 左前缀积 × 右后缀积；输出数组先存前缀，再倒着乘一个滚动后缀，不用除法、O(1) 额外空间
41. 缺失的第一个正数 · 困难 —— 答案必在 1..n+1，于是把数组本身当哈希表：值 v 归位到下标 v−1，再找第一个没归位的，O(n) 时间 O(1) 空间

矩阵

73. 矩阵置零 · 中等 —— 拿第一行第一列当标记数组省掉 O(m+n) 空间；先单独记下它们自己要不要清零，最后再处理
54. 螺旋矩阵 · 中等 —— 维护上下左右四条边界，一圈走四条边、每走完一条就把那条边界往里收，收过头即停，不用 visited
48. 旋转图像 · 中等 —— 顺时针转 90° = 沿主对角线转置 + 每行左右翻转；把旋转拆成两个自逆的对称操作，原地就好写
240. 搜索二维矩阵 II · 中等 —— 从右上角出发：它是行最大、列最小，每比一次就能删掉一整行或一整列，O(m+n)

链表

160. 相交链表 · 简单 —— 两个指针走完自己再走对方，路程都是 a+b+c，差值自己抵消；「拼接消长度差」比先数长度再对齐更短
206. 反转链表 · 简单 —— 三指针原地掉头：prev 是已反转部分的头，cur 是待处理部分的头，每步只翻一根 next；链表题的基本功模块
234. 回文链表 · 简单 —— 快慢指针找中点 + 反转后半段 + 双指针对比，三个链表模块拼出 O(1) 空间；单链表不能倒着走，就把后半段翻过来
141. 环形链表 · 简单 —— Floyd 判圈：快指针每步比慢指针多走 1，进了环就一定追上；O(1) 空间判环，任何「迭代函数」序列都能用
142. 环形链表 II · 中等 —— Floyd 相遇后，一个指针回起点、两个同速走，再相遇即入环点——由路程等式 a = (k-1)L + (L-b) 推出，不用背
21. 合并两个有序链表 · 简单 —— 哑节点 + 尾指针：每次摘两条链里较小的头接到尾巴上，一条走完就整段接上另一条；dummy 让「头节点是谁」不再需要特判
2. 两数相加 · 中等 —— 逆序存储就是竖式加法的天然顺序：逐位相加带进位，循环条件写成 l1 or l2 or carry，长度不等和最高位进位一并处理
19. 删除链表的倒数第 N 个结点 · 中等 —— 前后指针拉开固定间距，前者到底时后者正停在目标的前驱；「倒数第 k」一遍扫完，dummy 兜住删头节点
24. 两两交换链表中的节点 · 中等 —— 指针改接前先画清三根线：pre→b、a→b.next、b→a；以「一对的前驱」为循环变量，dummy 让第一对不特殊
25. K 个一组翻转链表 · 困难 —— 先探路数够 k 个再动手，组内用三指针反转、prev 初值设为下一组的头，反转完自动接好后路；组尾变组头，接前驱就完事
138. 随机链表的复制 · 中等 —— 深拷贝的本质是「原节点 → 新节点」的映射；哈希表显式存，或把副本插在原节点身后让 next 充当映射，O(1) 额外空间
148. 排序链表 · 中等 —— 链表排序首选归并：切分只需快慢指针、合并不要额外数组；想要 O(1) 空间就自底向上，按 1、2、4… 的步长切段两两合并
23. 合并 K 个升序链表 · 困难 —— k 路归并：堆里只放每条链当前的头，弹最小、补它的后继，O(N log k)；或两两分治合并，和归并排序同一棵递归树
146. LRU 缓存 · 中等 —— 哈希表管「O(1) 找到」，双向链表管「O(1) 挪位和淘汰」，两者存同一个节点；哨兵头尾让插入删除零特判

二叉树

94. 二叉树的中序遍历 · 简单 —— 递归改迭代的通用手法：显式栈模拟调用栈，「一路向左压栈，弹出即访问，转向右子树」
104. 二叉树的最大深度 · 简单 —— 树形递归的最小模板：信任子问题的返回值，只写「当前节点怎么合并左右答案」
226. 翻转二叉树 · 简单 —— 每个节点交换左右孩子，访问顺序无所谓——前序、后序、层序都对，唯独中序会换两次
101. 对称二叉树 · 简单 —— 一棵树的性质改写成两棵树的关系：双指针同时下行，外侧配外侧、内侧配内侧
543. 二叉树的直径 · 简单 —— 返回值与答案分离：递归返回「往下单边能走多深」，答案在每个拐点用「左深 + 右深」顺手更新
102. 二叉树的层序遍历 · 中等 —— BFS 分层的标准手法：每轮先记下 len(queue)，恰好弹这么多个——队列里天然只剩一整层
108. 将有序数组转换为二叉搜索树 · 简单 —— 有序数组取中点当根、两半递归建子树——BST 性质来自有序，平衡来自两半大小差不超过 1
98. 验证二叉搜索树 · 中等 —— 只比父子是错的——BST 约束是整棵子树的上下界，递归时把 (lo, hi) 开区间往下传
230. 二叉搜索树中第 K 小的元素 · 中等 —— BST 中序即升序，迭代中序数到第 k 个就停；频繁查询时给节点记子树大小，按排名二分下行
199. 二叉树的右视图 · 中等 —— 每层取最后一个：BFS 分层取队尾；DFS 先右后左，每个深度第一次到达的节点就是右视图
114. 二叉树展开为链表 · 中等 —— 原地改指针的前序展开：把左子树整段插到右边，接口是左子树的最右节点——每条边只走常数次，O(1) 空间
105. 从前序与中序遍历序列构造二叉树 · 中等 —— 前序给根，中序按根切成左右两段，段长反推前序的切分——哈希表存中序下标，建树 O(n)
437. 路径总和 III · 中等 —— 前缀和 + 哈希搬上树：根到当前节点就是一条「数组」，回溯时把前缀和计数撤掉，只留祖先链
236. 二叉树的最近公共祖先 · 中等 —— 后序往上报「子树里找到了谁」：左右各报一个的那个节点就是 LCA，只有一边报就原样上传
124. 二叉树中的最大路径和 · 困难 —— 543 直径的带权版：返回单边最大贡献（负的就截成 0 不接），答案在拐点用「根 + 左贡献 + 右贡献」结算

图论

200. 岛屿数量 · 中等 —— 数连通块 = 外层扫到一个没访问的陆地就计数 +1，再 flood fill 把整块淹掉；入队时就标记，每格只处理一次
994. 腐烂的橘子 · 中等 —— 多源 BFS：把所有起点一起放进队列当第 0 层，按层扩散，层数就是时间；最后查一遍有没有够不着的
207. 课程表 · 中等 —— 能否修完 = 有向图有没有环；Kahn 拓扑排序反复剥掉入度为 0 的点，剥不完就有环——DFS 三色标记是同一个判断的另一种写法
208. 实现 Trie (前缀树) · 中等 —— Trie 把共同前缀合并成共同路径，查询只和单词长度有关；节点上的 is_end 标记区分「走得到」和「是个词」——search 与 startsWith 只差这一位

回溯

46. 全排列 · 中等 —— 回溯的标准三件套——路径、选择列表、撤销；用 used 数组标记「已在路径上」，排列问题就是每层把没用过的都试一遍
78. 子集 · 中等 —— 子集 = 每个元素选或不选；回溯时每个节点都收答案、下一层只从 start 往后挑，顺序本身就是去重
17. 电话号码的字母组合 · 中等 —— 多组候选的笛卡尔积——第 i 层只从第 i 组里挑，回溯的层数由输入长度决定，不用 used 也不用 start
39. 组合总和 · 中等 —— 可重复选的组合：递归传 i 而不是 i+1 就允许重用，start 保证不回头；排序后一超 target 立刻 break
22. 括号生成 · 中等 —— 只生成合法前缀：左括号没用完就能放左，右括号少于左括号才能放右——剪枝条件就是合法性的不变量
79. 单词搜索 · 中等 —— 网格回溯：进格子时原地打标记、出来时还原，用 board 本身当 visited；匹配失败立刻返回，一格一字符地剪
131. 分割回文串 · 中等 —— 切割问题 = 枚举下一刀切在哪；先用区间 DP 把「s[i..j] 是否回文」打成表，回溯时判回文降到 O(1)
51. N 皇后 · 困难 —— 一行放一个皇后把二维搜索压成排列；列、主对角线 r-c、副对角线 r+c 各一个集合，冲突判定 O(1)

二分查找

35. 搜索插入位置 · 简单 —— 所有二分都写成「找第一个满足条件的位置」——左闭右开 [lo, hi)，循环结束 lo 就是答案，插入位置、lower_bound 一套模板
74. 搜索二维矩阵 · 中等 —— 逐行有序且首尾相接的矩阵就是一条拉平的有序数组；下标 k 映射回 (k // n, k % n)，一次二分搞定
34. 在排序数组中查找元素的第一个和最后一个位置 · 中等 —— 左右边界不写两套二分——只写一个 lower_bound，右边界 = lower_bound(target + 1) - 1
33. 搜索旋转排序数组 · 中等 —— 旋转数组从任意 mid 切开，总有一半是有序的——只在有序那半里判断 target 在不在，不在就去另一半
153. 寻找旋转排序数组中的最小值 · 中等 —— 拿末尾元素当标尺，「nums[i] <= nums[-1]」在旋转数组上是单调谓词 F…FT…T，最小值就是第一个 T
4. 寻找两个正序数组的中位数 · 困难 —— 不二分值，二分「短数组切在哪」：左半凑够一半元素后，切口合法等价于交叉比较两对边界，这个条件对切口位置单调

栈

20. 有效的括号 · 简单 —— 嵌套结构的匹配靠栈：左括号入栈，右括号必须和栈顶配对；最后栈空才算合法，别漏了只有左括号的情况
155. 最小栈 · 中等 —— 每个元素入栈时顺手记下「截至此刻的最小值」；栈只在顶端变动，所以历史最小值跟着一起弹就永远正确
394. 字符串解码 · 中等 —— 嵌套的 k[...] 用栈保存「外层上下文」：遇 [ 把当前串和倍数压栈、清空重来，遇 ] 弹出外层拼回去
739. 每日温度 · 中等 —— 「下一个更大元素」的标准答案是单调栈：栈里存还没等到答案的下标，新元素一来就把比它小的全部结算
84. 柱状图中最大的矩形 · 困难 —— 枚举「谁是最矮的那根」：每根柱子向两侧延伸到第一个更矮的为止，单调递增栈弹出时左右边界一次拿齐

堆

215. 数组中的第K个最大元素 · 中等 —— Top-k 两把刀：大小为 k 的小顶堆 O(n log k)，快速选择平均 O(n)；三路划分防住大量重复元素的退化
347. 前 K 个高频元素 · 中等 —— 先计数再选 top-k：大小为 k 的堆 O(n log k)；频次上界是 n，按频次分桶倒着捡，O(n)
295. 数据流的中位数 · 困难 —— 对顶堆：大顶堆装较小一半、小顶堆装较大一半，大小差不超过 1——中位数永远在两个堆顶

贪心算法

121. 买卖股票的最佳时机 · 简单 —— 固定卖出日，买入日只需是前缀最小值——一遍扫描维护「至今最低价」，O(n) O(1)
55. 跳跃游戏 · 中等 —— 只维护「最远能到哪」一个数：可达区间必然连续，扫到够不着的位置就失败
45. 跳跃游戏 II · 中等 —— 隐式 BFS：当前跳数能覆盖的区间是一层，走到层边界才加一跳，下一层边界取层内最远可达
763. 划分字母区间 · 中等 —— 先记每个字母最后出现的位置，扫描时把当前段的右界推到段内字母的最远末次出现，走到右界就切一刀

动态规划

70. 爬楼梯 · 简单 —— 按最后一步分类计数：到第 n 阶的走法 = 到 n-1 阶 + 到 n-2 阶，斐波那契，滚动两个变量
118. 杨辉三角 · 简单 —— 每行两端是 1，中间每个数等于上一行肩上两数之和——最朴素的「由上一行推下一行」的 DP
198. 打家劫舍 · 中等 —— 按「最后一间抢不抢」分两类：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，选或不选型 DP 的原型
279. 完全平方数 · 中等 —— 完全平方数当硬币、n 当金额，就是「凑出 n 的最少硬币数」——完全背包求最值
322. 零钱兑换 · 中等 —— 完全背包求最值：dp[a] = 1 + min(dp[a - c])，用 amount+1 当「凑不出」的哨兵，省掉无穷大判断
139. 单词拆分 · 中等 —— dp[i] 表示前缀 s[:i] 能否拆完；枚举最后一个单词的起点 j，只要 dp[j] 且 s[j:i] 在字典里就成
300. 最长递增子序列 · 中等 —— O(n²) 的 dp[i] 以 i 结尾；O(n log n) 换个状态——tails[k] 存长度 k+1 的递增子序列的最小结尾，二分替换
152. 乘积最大子数组 · 中等 —— 负数会让最小变最大，所以以 i 结尾同时维护最大积和最小积两个状态，遇到负数二者互换角色
416. 分割等和子集 · 中等 —— 转成 0-1 背包：能否选出和为 sum/2 的子集；一维布尔数组倒序更新，保证每个数只用一次
32. 最长有效括号 · 困难 —— 栈里存「最后一个没配上的位置」当分界；每配上一个右括号，当前下标减栈顶就是以它结尾的有效长度

多维动态规划

62. 不同路径 · 中等 —— 网格计数 DP：每格路径数 = 上方 + 左方，一行滚动数组就够；本质是组合数 C(m+n-2, m-1)
64. 最小路径和 · 中等 —— 网格最值 DP：dp[i][j] = grid[i][j] + min(上, 左)，第一行第一列只能单向累加，滚动成一行
5. 最长回文子串 · 中等 —— 回文由中心向外对称生长：枚举 2n-1 个中心各扩一次，O(n²) 时间 O(1) 空间，比区间 DP 省表
1143. 最长公共子序列 · 中等 —— 双序列 DP 的母题：dp[i][j] 看两个前缀，末字符相等就对角线 +1，否则各退一位取大
72. 编辑距离 · 中等 —— 双前缀 DP：末字符相等就免费走对角线，否则在增、删、改三个方向里取最小 +1；空串那行列是初值

技巧

136. 只出现一次的数字 · 简单 —— 异或自反：x ^ x = 0、x ^ 0 = x，且满足交换律——全体异或一遍，成对的互相抵消，剩下落单的
169. 多数元素 · 简单 —— Boyer-Moore 投票：不同的数两两抵消，多数元素超过一半，抵消到最后一定还剩它，O(n) O(1)
75. 颜色分类 · 中等 —— 荷兰国旗三指针：[0,p0) 全 0、[p0,i) 全 1、(p2,n) 全 2，i 扫到 p2 为止；换来的 2 侧元素没看过，i 不前进
31. 下一个排列 · 中等 —— 从右找第一个下降点 i，再从右找第一个比它大的数交换，最后把 i 之后的降序段反转成升序——增幅最小的那一步
287. 寻找重复数 · 中等 —— 把 i → nums[i] 看成链表的 next 指针，重复值就是环的入口——Floyd 快慢指针，不改数组、O(1) 空间

「热题 100」，2026-09-29 读。 ↩