知识点专题

用 O(1) 的查找把「是否出现过 / 出现几次 / 配对」类问题从暴力 O(n²) 降到 O(n)，是刷题最高频的工具。

用两个下标在有序数组 / 链表上相向或同向移动，省去一层循环。常用于求和、去重、判回文、链表快慢指针。

维护一个「合法区间」随右端扩张、左端收缩，求最长 / 最短 / 定长子串子数组。双指针的进阶套路。

预处理前缀和后，任意区间和都能 O(1) 求出；差分则把「区间整体加减」变成端点操作。

在「单调」的答案空间里每次砍掉一半。不止用于查值，更常用于「二分答案」——把求最优转成判定可行。

排序本身是基础，但「排完序之后」常常让贪心、双指针、去重变得显然。重点是想清楚按什么排。

解析、匹配、模拟类题目的高频载体。重点是把题意拆成清晰的边界与状态。

gcd / 质数 / 快速幂 / 组合数等基础数论与技巧，常以「看穿规律」的形式出现在笔试里。

用二进制位直接操作，常用于状态压缩、集合表示，以及一些「异或消消乐」式的巧解。

递归天然契合树。遍历（前中后序 / 层序）是地基，很多题是「在遍历时顺手维护一点信息」。

一条路走到底再回头。用于连通块、网格岛屿、全排列子集，以及一切「枚举所有可能」的搜索。

一圈一圈往外扩。无权图 / 网格里求「最短步数 / 最少操作」的首选。

DFS + 撤销选择，系统地枚举所有候选解。排列、组合、子集、棋盘类问题的统一框架。

每一步都做当前最优的选择。难点不在写代码，而在「证明局部最优能导出全局最优」。

把大问题拆成重叠子问题，用「状态 + 转移」自底向上推。面试最能拉开差距的板块。

DP 里最成体系的一类：0/1 背包、完全背包、多重背包，以及它们的容量 / 价值 / 计数变体。

状态是一段区间 dp[i][j]，通过枚举分割点合并子区间。石子合并、回文、括号类问题常用。

建图 + 遍历是一切图论题的起点。连通性、二分图、欧拉路都建立在 DFS / BFS 之上。

带权图求最短距离。Dijkstra（非负权）、Bellman-Ford / SPFA（含负权）、Floyd（多源）各有适用场景。

在有向无环图上求一个「先后顺序」。课程表、任务依赖、判断是否成环的标准解法。

后进先出。用于括号匹配、表达式求值、撤销类问题，以及把「就近的配对」关系顺手记下来。

维护一个单调递增 / 递减的栈，O(n) 求出每个元素「下一个更大 / 更小」的位置。柱状图、温度、接雨水的核心。

先进先出。BFS 的载体；单调队列则能 O(n) 求滑动窗口最大值。

每次 O(log n) 取出最大 / 最小。Top-K、第 K 大、合并多个有序序列、Dijkstra 都靠它。

近 O(1) 地合并集合、判断两点是否连通。处理「连通块 / 朋友圈 / 是否成环」类问题的利器。