算法技巧

基础知识 ⭐ 入门 🔥 高频

💡 核心要点

很多题不是“不会做”，而是“没有识别出信号”。真正稳定的第一反应，不只是想到方法，还要同时判断这个数据范围允许什么复杂度。

概念

• 题型识别不是背题库，而是把“题目特征”和“常用方法”建立稳定映射。
• 一道题往往不只属于一种方法，但通常会有一个最先应该想到的入口。
• 复杂度判断不应该脱离题型识别单独背，而应该和方法一起看。
• 先识别信号，再看数据范围，再选数据结构和算法，比上来就硬套模板更稳。

怎么处理

1. 先看输入结构：数组、字符串、链表、树还是图。
2. 再看目标：求最短、求最多、求是否存在、求方案数还是求第 大。
3. 再看题目信号：有序、连续区间、去重计数、依赖关系、Top K、连通性、是否需要枚举全部方案。
4. 最后把这些信号和数据范围一起映射到 1 到 2 个优先尝试的方法。

题目特征、复杂度与方法总表

题目特征	常见复杂度目标	优先方法	常用结构	常见场景
，要枚举所有方案、排列、子集	指数级通常可接受	回溯、状态压缩、位运算枚举	path、visited、bitmask	全排列、子集、组合
或 ，要比较两两关系	往往还能接受	双重枚举、基础 DP	二维数组、双循环	二元组统计、区间 DP
数组有序，或者答案满足单调性	或	二分查找、二分答案	下标、边界指针	查找边界、最小可行值
连续子数组、连续子串、最短覆盖		滑动窗口、双指针、前缀和	left/right、计数表	最长不重复子串、最短覆盖
去重、计数、配对、状态映射		哈希表	Map、Set	两数之和、字母异位词
多次区间求和查询	预处理 ，查询	前缀和	prefix[]	区间和、子数组统计
多次区间批量加减		差分	diff[]	航班预订、批量修改
最少步数、无权最短路、层级扩展		BFS	队列、visited[]	最少操作次数、棋盘最短路
正权最短路		Dijkstra	堆、dist[]	网络延迟、最短路径
遍历所有节点、路径、连通块		DFS、BFS	递归栈、队列	岛屿问题、图遍历
有依赖顺序、先后约束		拓扑排序	入度数组、队列	课程表、任务编排
动态维护最值、前 个元素	或单次	堆、优先队列	最小堆、最大堆	Top K、数据流中位数
排序后关系更清晰		排序 + 扫描 / 双指针	排序数组	合并区间、三数之和
局部最优有机会推出全局最优	或	贪心	排序、指针	区间调度、跳跃游戏
当前选择会影响后续最优，存在重叠子问题	看状态数，常见为 、	动态规划	dp[]、状态表	打家劫舍、最长子序列
树上要算子树信息、路径信息、递归返回值	常见	树 DFS、树形 DP	递归函数、邻接表	二叉树路径和、子树问题
多个点逐步合并成组	接近线性	并查集	parent[]、rank[]	连通块、冗余连接

复杂度速判

1. 如果 到了 级别，通常要优先考虑 或 。
2. 如果题目有多组测试，不要只看单组规模，要看总输入规模。
3. 两层循环不一定就是 ，如果两个指针都单调前进，整体仍可能是 。
4. 排序的 在很多 级别题里是可以接受的，不要因为“不是线性”就先排除。
5. 先定复杂度上限，再选方法，会比先写代码再回头算复杂度更稳。

常见误区

1. 只看题目表面类型，比如“这是数组题”，却不看它真正的触发信号。
2. 只想到方法名字，却没有同步判断这个数据范围是否允许这种复杂度。
3. 一个方法没做出来就立刻换题解，没有先确认是不是入口判断错了。
4. 只记结论，不总结“为什么这题会让我想到这个方法”。

这一页的目标

• 先建立“题目特征 + 数据范围 -> 方法入口 + 复杂度上限”的第一反应。
• 后续看数组、图、动态规划等章节时，再把这里的总表和具体题型对应起来。