lc hot100

定位：写不出代码时，也能讲清思路、写出伪代码。 每个板块含：识别信号 → 核心思路 → 模板骨架 → 易错点。

目录

1. 哈希 Hash
2. 双指针 Two Pointers
3. 滑动窗口 Sliding Window
4. 子串 / 前缀和
5. 普通数组
6. 矩阵 Matrix
7. 链表 Linked List
8. 二叉树 Binary Tree
9. 图论 Graph
10. 回溯 Backtracking
11. 二分查找 Binary Search
12. 栈 Stack
13. 堆 Heap
14. 贪心 Greedy
15. 动态规划 DP
16. 通用心法

1. 哈希 Hash

识别信号：需要「快速查某个东西在不在 / 出现几次 / 配对」；O(1) 查找。

核心思路：用 dict（键值映射）或 set（去重、查在不在）把「查找」从 O(n) 降到 O(1)。用空间换时间。

模板骨架：

seen = {}                      # 或 set()
for x in nums:
    if 需要的东西 in seen:      # O(1) 查
        ...
    seen[x] = ...              # 记账

代表题：

• 1 两数之和：dict 存「值→下标」，查 target - x 在不在。
• 49 字母异位词分组：排序后的字符串当「指纹」做 key，defaultdict(list) 归组。
• 128 最长连续序列：set 存所有数，只从「序列起点」（x-1 不在 set）往上数。

易错点：defaultdict(list) / Counter 省事；空集合是 set() 不是 {}。

2. 双指针 Two Pointers

识别信号：有序数组 / 首尾逼近 / 原地操作 / 找两数配对。

核心思路：两个指针（快慢 or 对撞）协同移动，一次遍历解决，O(n)。

两种范式：

• 快慢指针：一个走得快、一个走得慢，常用于原地移动元素。
• 对撞指针：left 从头、right 从尾，往中间夹。

模板骨架：

# 对撞
left, right = 0, len(nums) - 1
while left < right:
    if 条件: left += 1
    else: right -= 1

代表题：

• 283 移动零：快慢指针，慢指针放非零。
• 11 盛水最多容器：对撞，移动较矮的墙（矮墙是瓶颈）。
• 15 三数之和：排序 + 固定一个 + 对撞找另两个 + 去重。
• 42 接雨水：对撞 + left_max/right_max，处理较矮的一侧。

易错点：三数之和要排序、要跳过重复；接雨水「处理较矮侧」。

3. 滑动窗口 Sliding Window

识别信号：求「连续子数组 / 子串」的最长、最短、满足某条件。

核心思路：一个窗口 [left, right]，右指针扩张、左指针收缩，动态维护窗口内的状态。

模板骨架：

left = 0
for right in range(len(s)):
    加入 s[right] 到窗口
    while 窗口不合法:
        移出 s[left]
        left += 1
    更新答案（此时窗口合法）

代表题：

• 3 无重复最长子串：窗口内不能有重复字符，用 set/dict。
• 438 找异位词：固定大小窗口 + Counter 比较。
• 76 最小覆盖子串：可变窗口 + need/have 计数，凑齐就收缩。

易错点：想清楚「窗口何时收缩」；固定窗口 vs 可变窗口。

4. 子串 / 前缀和

识别信号：连续子数组「和为 K」/ 区间和 / 计数。

核心思路：前缀和 + 哈希。prefix[i] = 前 i 个数的和；「子数组和为 k」= 找 prefix[j] - prefix[i] = k，即查 prefix - k 在不在哈希表。

模板骨架：

from collections import defaultdict
seen = defaultdict(int)
seen[0] = 1              # 空前缀
cur = 0
for x in nums:
    cur += x
    ans += seen[cur - k]  # 之前有几个 prefix = cur-k
    seen[cur] += 1

代表题：

• 560 和为 K 的子数组：前缀和 + 哈希「记账本」。
• 239 滑动窗口最大值：单调队列（deque，队头是最大值）。
• 76 最小覆盖子串：见滑动窗口。

易错点：seen[0]=1 别忘；239 用单调递减队列。

5. 普通数组

识别信号：数组上的经典技巧题（最大子数组、区间、原地哈希）。

代表题 & 一句话思路：

• 53 最大子数组和：Kadane，cur = max(x, cur+x)，边走边刷新最大。
• 56 合并区间：按起点排序，能重叠就合并。
• 189 轮转数组：三次反转（整体反 → 前 k 反 → 后 n-k 反）。
• 238 除自身外乘积：前缀积 × 后缀积，不用除法。
• 41 缺失的第一个正数：原地哈希（值 v 放到下标 v-1 的「座位」），再找第一个不对位的。

易错点：区间题先排序；41 的「座位表」值 v ↔ 下标 v-1。

6. 矩阵 Matrix

识别信号：二维网格操作、旋转、螺旋、搜索。

基础：m=len(matrix), n=len(matrix[0]), matrix[i][j]；四方向 dirs=[(-1,0),(1,0),(0,-1),(0,1)]；避免 [[0]*n]*m 陷阱。

代表题 & 一句话思路：

• 73 矩阵置零：先用两个 set 记要清零的行/列，再统一清。
• 54 螺旋矩阵：四个边界 top/bottom/left/right 收缩。
• 48 旋转图像：转置 + 每行反转。
• 240 搜索二维矩阵 II：从右上角出发，大了往左、小了往下（阶梯搜索）。

易错点：240 从右上角（或左下角）走；48 转置再反转。

7. 链表 Linked List

识别信号：涉及 ListNode、next、指针操作。

核心武器：

• 虚拟头 dummy：dummy = ListNode(0)，避免处理头节点特判。
• 快慢指针：找中点、找环、找倒数第 k 个。
• 三指针反转：prev/cur/nxt。

模板骨架：

# 遍历
cur = head
while cur:
    cur = cur.next

# 反转
prev = None
while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt

代表题 & 一句话思路：

• 206 反转链表：三指针 prev/cur/nxt。
• 141/142 环形链表：快慢指针；142 相遇后从头再走找入口（a=c）。
• 21 合并两个有序链表：dummy + 谁小接谁。
• 19 删除倒数第 N 个：快指针先走 n 步 + dummy。
• 24 两两交换、25 K 个一组翻转：dummy + 局部反转再接线。
• 148 排序链表：归并（快慢找中点切开 + merge）。
• 23 合并 K 个：两两配对分治 merge，或用堆。
• 146 LRU：哈希表 + 双向链表（用到就移到头，满了删尾）。

易错点：链表题几乎都用 dummy；快慢指针注意 while fast and fast.next。

8. 二叉树 Binary Tree

识别信号：TreeNode、left/right、递归。

核心心法：信任递归——只想两件事：① 终止条件（通常 if not node: return）；② 当前层如何组合左右子树的结果。

四种遍历：

# 前序 根左右 / 中序 左根右 / 后序 左右根：只差 append 位置
def dfs(node):
    if not node: return
    dfs(node.left); res.append(node.val); dfs(node.right)  # 中序

# 层序：队列 BFS
from collections import deque
q = deque([root])
while q:
    size = len(q)            # 锁定这一层
    for _ in range(size):
        node = q.popleft()
        ...
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)

关键性质：BST 的中序遍历 = 升序（94/98/230 都靠它）。

代表题 & 一句话思路：

• 104 最大深度：1 + max(左, 右)。
• 226 翻转：交换左右孩子 + 递归。
• 101 对称：双指针递归，交叉比较 a.left↔b.right。
• 543 直径 / 124 最大路径和：边求深度边刷新全局答案；更新用「左+右」，返回用「max(左,右)」；124 负贡献舍弃（max(gain,0)）。
• 102 层序 / 199 右视图：队列 + size 分层；右视图取每层最后一个。
• 108 有序数组转 BST：取中点当根，递归建左右。
• 98 验证 BST：传上下界（往左收上界、往右收下界）；或中序升序。
• 230 第 K 小：中序遍历数到第 k 个。
• 114 展开为链表：递归展开左右，接线。
• 105 前序中序建树：前序定根，中序分左右（哈希存中序下标）。
• 437 路径总和 III：前缀和 + 哈希 + 回溯撤销（560 搬到树上）。
• 236 最近公共祖先：向上汇报——碰到 p/q 或空返回，左右都汇报到 → 当前是 LCA。

易错点：98 不能只比父子（要传区间）；124/543 区分「更新答案」和「往上返回」。

9. 图论 Graph

识别信号：网格连通块、依赖顺序、最少步数扩散。

两把武器：

• DFS（递归，同二叉树）：一条路走到底，必须标记已访问否则死循环。
• BFS（队列，同层序）：一层层扩散，适合最少步数/最短路径。

网格 DFS 模板：

def dfs(i, j):
    if i<0 or i>=m or j<0 or j>=n or grid[i][j] != '1':
        return
    grid[i][j] = '0'          # 标记已访问（关键！漏了会死循环=超时）
    dfs(i-1,j); dfs(i+1,j); dfs(i,j-1); dfs(i,j+1)

多源 BFS 模板（求最少步数/时间）：

q = deque(所有起点)
while q and 还有目标:
    minutes += 1
    for _ in range(len(q)):     # 每层=一步/一分钟
        ... 扩散到四邻，标记，入队

代表题 & 一句话思路：

• 200 岛屿数量：DFS 淹岛，遇到未淹的 ‘1’ 就 count+1 并淹掉整片。
• 994 腐烂橘子：多源 BFS，所有腐烂橘子一起入队，每层=一分钟，fresh 计数。
• 207 课程表：拓扑排序（BFS+入度）——入度 0 入队，学一门解锁后继，学完总数=无环。

易错点：网格 DFS 必须标记访问（超时=八成漏标记）；BFS 每轮先 size=len(q) 分层；拓扑排序靠「环里节点入度降不到 0」检测环。

10. 回溯 Backtracking

识别信号：「列出所有 组合/排列/方案/分割」；穷举所有可能。

核心 = DFS + 撤销选择。判断是不是回溯：有没有「改状态 → 递归 → 改回来」。

通用模板：

def backtrack(路径, 选择列表):
    if 结束条件:
        res.append(路径[:])     # 拷贝！否则被后续修改
        return
    for 选择 in 选择列表:
        做选择（path.append）
        backtrack(...)          # 递归
        撤销选择（path.pop）     # 回溯

三种变体的区别： | 类型 | 防重复/推进方式 | |—|—| | 排列（46）| used[] 标记，每层从 0 选、跳过已用；填满才记录 | | 子集/组合（78/39）| start 参数只往后选；子集每步都记录 | | 可重复选（39）| 递归传 i（不是 i+1）|

代表题 & 一句话思路：

• 46 全排列：used 标记。
• 78 子集：start + 每步记录。
• 17 电话号码：映射表逐位选。
• 39 组合总和：传 i 可重复 + remain 剩余量 + 排序后 if x>remain: break 剪枝。
• 22 括号生成：剪枝 open<n 才加左、close<open 才加右。
• 79 单词搜索：网格 DFS + 撤销标记（走过 '#'，回来恢复）。
• 131 分割回文串：枚举切点，只有回文才切下去。
• 51 N 皇后：逐行放，cols/diag1(row-col)/diag2(row+col) 三集合剪枝。

易错点：path[:] 拷贝、pop() 加括号；排列用 used、组合用 start；「传 i vs i+1」决定能否重复选。

11. 二分查找 Binary Search

识别信号：有序 / 找边界 / O(log n) / 在单调性上找分界。

三大命门：区间定义 ↔ 循环条件 ↔ 边界更新，必须自洽。

模板 A：找值（闭区间）：

left, right = 0, len(nums) - 1
while left <= right:            # 闭区间用 <=
    mid = (left + right) // 2
    if nums[mid] == target: return mid
    elif nums[mid] < target: left = mid + 1
    else: right = mid - 1
return -1                       # 或 return left（插入位置）

模板 B：找边界（收拢）：

while left < right:             # 用 <
    mid = (left + right) // 2
    if 条件: left = mid + 1
    else: right = mid           # 保留 mid（可能是答案）
return left

代表题 & 一句话思路：

• 35 搜索插入位置：找不到 return left（插入点）。
• 74 搜索二维矩阵：拉直成一维二分，matrix[mid//n][mid%n]。
• 34 第一个和最后一个位置：双二分，相等时一个往左收、一个往右收。
• 33 搜索旋转数组：先判断哪半有序，再看 target 在不在那半。
• 153 找最小值：mid 和 nums[right] 比，大了去右（left=mid+1），小了保留（right=mid）。
• 4 两数组中位数（难）：找第 k 小，每次排除 k/2 个。

易错点：区间定义和循环条件配套；边界 mid±1 别写成 mid（死循环）；旋转数组「先找有序半」。

12. 栈 Stack

识别信号：配对/嵌套（括号）、下一个更大/更小（单调栈）、表达式、嵌套解码。

用 list 即可：append（入）、pop()（出）、stack[-1]（看顶）。

两大招牌：

• 括号/配对匹配：左括号入栈，右括号配栈顶（后开先闭）。
• 单调栈：栈里保持单调，找「下一个更大/更小」。

括号匹配模板：

stack = []
pairs = {')':'(', ']':'[', '}':'{'}
for ch in s:
    if ch in '([{': stack.append(ch)
    else:
        if not stack or stack[-1] != pairs[ch]: return False
        stack.pop()
return not stack               # 栈空才合法

代表题 & 一句话思路：

• 20 有效括号：左入栈、右配栈顶。
• 155 最小栈：主栈 + 辅助栈（min_stack 同步涨落，栈顶永远是最小）。
• 394 字符串解码：遇 [ 压外层状态、遇 ] 弹栈重复 k 次拼回（嵌套用栈）。
• 739 每日温度：单调栈（存下标，找下一个更暖的）。

易错点：右括号先判栈空；嵌套结构「进入压栈、退出弹栈」。

13. 堆 Heap

识别信号：反复取最大/最小值、Top K、动态维护极值。

Python heapq（小顶堆）：heappush（加）、heappop（弹最小）、heap[0]（看最小）。

• 要大顶堆 → 存负数。
• 按属性排 → 存元组 (属性, 数据)（按第一项比较）。

Top K 模板（第 K 大 → 大小为 K 的小顶堆）：

import heapq
heap = []
for x in nums:
    heapq.heappush(heap, x)
    if len(heap) > k:
        heapq.heappop(heap)     # 超 K 弹最小
return heap[0]                  # 堆顶=第 K 大

代表题 & 一句话思路：

• 215 第 K 大：大小 K 的小顶堆，堆顶=第 K 大。
• 347 前 K 高频：Counter 数频率 + 堆存 (频率, 元素)。
• 295 数据流中位数：双堆（大顶堆管左半、小顶堆管右半）。

易错点：求「第 K 大」用「小顶堆」（反直觉）；大顶堆存负数。

14. 贪心 Greedy

识别信号：求最值 / 能否达成，且「每步选当前最优」能推出全局最优。

核心难点：判断能不能贪——多举例、主动找反例。一个反例就推翻。

常见套路：排序 + 贪心；维护「当前最优量」（最远、最低价…）；区间问题按端点排序。

代表题 & 一句话思路：

• 121 买卖股票 I：维护「最低价」，每天试卖（先算利润再更新最低价）。
• 55 跳跃游戏：维护 farthest 最远可达，i > farthest 则失败。
• 45 跳跃游戏 II：贪心求最少跳数（在当前可达范围内选下一跳最远的）。
• 56 合并区间：排序后贪心合并（也算区间贪心）。

易错点：贪心不一定对，先找反例；不确定用 DP 更稳。

15. 动态规划 DP

识别信号：求最值 / 方案数 / 能否达成，且「每步选择影响后续」+ 有重叠子问题。

五步框架（背下来！）：

1. 定义状态 dp[i]（最难、最关键）
2. 状态转移方程（当前如何由更小的推出）
3. 初始值 base case
4. 计算顺序（通常从小到大，保证依赖已算好）
5. 返回值（通常 dp[n]）

几维？ 看「描述一个子问题要几个变量」：一个字符串/数组常一维；两个序列或「物品+容量」常二维。

一维模板：

dp = [0] * (n + 1)
dp[0], dp[1] = 初始值
for i in range(2, n + 1):
    dp[i] = f(dp[i-1], dp[i-2], ...)   # 转移方程
return dp[n]

代表题 & 一句话思路：

• 70 爬楼梯：dp[i] = dp[i-1] + dp[i-2]。
• 118 杨辉三角：每行由上一行相邻两数相加。
• 198 打家劫舍：dp[i] = max(dp[i-1], dp[i-2] + nums[i])（偷不偷第 i 家）。
• 53 最大子数组和：dp[i] = max(nums[i], dp[i-1]+nums[i])（Kadane）。
• 322 零钱兑换、416 分割等和子集：背包。
• 1143 最长公共子序列、72 编辑距离：二维（两序列）。
• 62 不同路径、64 最小路径和：网格 DP。
• 5 最长回文子串、139 单词拆分：字符串 DP。

易错点：难点永远在「定义状态」和「转移方程」；可用滚动变量把空间优化到 O(1)。

DP vs 回溯 vs 贪心：

• 回溯：试所有可能，列出所有方案（慢、通用）。
• DP：存子问题答案复用，求最值/计数（有重叠子问题）。
• 贪心：每步选当前最优（DP 的特例，最快但要证明）。
• 关系：能贪心 ⊂ 能 DP ⊂ 能回溯。

16. 通用心法

拿到题先问自己：

1. 数据有序吗？→ 想二分 / 双指针。
2. 求连续子数组/子串？→ 滑动窗口 / 前缀和。
3. 求所有方案？→ 回溯。
4. 求最值/方案数且有重叠子问题？→ DP（先想能不能贪）。
5. 反复取极值 / Top K？→ 堆。
6. 配对/嵌套？→ 栈。
7. 树/图遍历？→ DFS（递归）/ BFS（队列），图要标记访问。
8. 需要快速查找？→ 哈希。

面试讲思路的套路（写不出代码也能拿分）：

1. 复述题意 + 举个小例子。
2. 说暴力解 + 它的复杂度瓶颈。
3. 说优化思路（用了哪个板块的什么技巧）。
4. 讲清「状态/指针/窗口」怎么定义、怎么转移。
5. 说复杂度。
6. 提边界情况（空输入、单元素、越界）。

高频易错清单：

• path[:] 拷贝、.pop() 加括号。
• 二分：区间 ↔ 循环条件 ↔ 边界更新自洽。
• 网格 DFS：标记已访问（否则死循环）。
• BFS：每轮先 size = len(q) 分层。
• 空集合 set()（{} 是空字典）。
• 链表：善用 dummy 虚拟头。
• DP：先想清楚「dp[i] 到底代表什么」。