前阵子有个刚转方向的朋友找我聊天说他刷了将近两百道题可一遇到没见过的题型还是发懵写完的代码不是超时就是边界出错。我让他随手写个二分查找他憋了半天写出了三个版本一个死循环一个漏掉了最后一个元素还有一个在数组为空时直接崩掉。问题不在他不够努力而在于他把算法当成了一堆彼此独立的知识点去背而不是当成一套需要逐层打磨的能力去练。这篇文章我想聊的就是我这些年带人、也带自己走过来的一条入门路径。我把它戏称为算法修炼之练气篇而练气十层指的是入门阶段需要打通的十个能力台阶。这套划分不按教材章节走而是按你能独立写出什么来定层。它适合刚接触数据结构和算法的人也适合刷了题但总觉得地基不牢的人。看完之后你至少能清楚地知道自己现在卡在第几层以及上一层需要补什么。1. 把算法入门拆成十层这套划分到底怎么来的1.1 为什么按层排而不是按知识点排教材的组织方式是按知识块来的数组、链表、栈、队列、树、图、排序、查找一块一块往下讲。这种方式适合系统学习但有个副作用——它让人误以为这些块是平的学完数组就等于和学完图站在同一水平线上。实际不是。能力的成长是立体的有些东西你没打通后面所有的东西都会变形。我举个很常见的例子。有人能背出归并排序的模板但你让他解释为什么要额外开一个数组、为什么它稳定而快排不稳定他答不上来。这说明他停在了抄写层没到理解层。再比如有人会用unordered_map做两数之和但一旦数据范围变成 10^9、内存吃紧他就不知道换什么结构了因为他从来没想过哈希表是在拿什么换什么。按层排的好处是每一层都有一个明确的能力标志不是我知道这个东西而是我能在不看模板的情况下写出边界正确、复杂度达标、还能说清为什么这样写的代码。这个标准说起来简单卡住的人一大片。1.2 练气十层的具体划分与自测方法下面这张表是我自己用的分法。层数不是严格的先后顺序前一层没稳后一层也能学但会一直返工。层数能力标志典型场景一层能一眼估出循环的复杂度判断暴力解法会不会超时二层数组与字符串的原地操作不出错反转、去重、原地压缩三层链表增删改查不丢指针反转链表、合并有序链表四层手写冒泡、插入、选择并说清差异理解稳定性与近乎有序场景五层独立写出归并、快排、堆排分治思想的第一次落地六层二分查找一次写对含四种变体查找边界、旋转数组七层能用哈希把查找降到 O(1)两数之和、去重计数八层会用双指针与滑动窗口降维最长无重复子串九层前缀和、差分随手就来区间求和、区间加十层递归出口清晰能写简单 DP爬楼梯、背包入门自测的方法很土但有效找一张白纸把每一层对应的经典题写一遍不看任何资料写完自己造三组数据——最小规模、最大规模、边界空、单元素、全相同。能全过这层就算过了只要有一组崩就老老实实回头补。提示自测时不要用在线判题直接用白纸或者纯文本编辑器。IDE 的自动补全和报错会替你兜底掩盖掉真实的记忆漏洞。2. 一到四层复杂度直觉、数组链表与三种基础排序2.1 复杂度是数出来的不是背出来的很多人背了一堆结论快排 O(n log n)、冒泡 O(n²)、二分 O(log n)。背结论没问题但一旦题目变形结论就对不上了。真正靠谱的做法是学会数循环。方法很朴素看最内层的语句被执行了多少次。单层循环遍历 n 个元素就是 n 次。两层嵌套外层 n 次、内层也 n 次就是 n × n。如果内层不是每次都跑满而是每次减半那对数就出现了。打个生活化的比方。你要在一个排好序的名单里找一个人。从头一个个看最坏要看完整本这是 O(n)。如果你每次都翻到中间比较一下目标在左半还是右半然后丢掉一半继续那每翻一次名单就短一半翻的次数就是 log₂n。一万人的名单最多翻 14 次。这个差距就是算法存在的意义。我见过太多人写双重循环时毫无知觉题目数据量给到 10^5他写出 O(n²) 的代码跑起来要几秒甚至几十秒然后开始怀疑是不是编译器的问题。其实不是编译器的问题是他在第一层就没站稳。经验上1 秒能承受的量级大致是10^8 次简单运算或者 10^7 次带一点分支的运算。拿这个数去除你就能立刻判断暴力解行不行。2.2 数组与链表内存布局决定了一切操作成本数组和链表的区别说到底就是内存连续不连续。数组是一整块连续内存所以按下标访问是 O(1)因为地址可以直接算出来首地址加上下标乘以元素大小。链表每个节点是散落的靠指针串起来所以想访问第 k 个必须从头走 k 步是 O(k)。这个差异直接决定了操作的取舍。数组在尾部插入是 O(1)在中间插入要搬动后面所有元素是 O(n)链表在已知位置插入是 O(1)但要先找到那个位置整体还是 O(n)。删除同理。操作数组单链表按下标访问O(1)O(n)头部插入O(n)O(1)尾部插入O(1)均摊O(1)有尾指针中间插入/删除O(n)O(1)已知前驱缓存友好度高低最后一行经常被忽略但它很关键。数组的连续内存能吃到 CPU 缓存的红利实际跑起来比理论复杂度看起来的还要快。链表虽然理论上删除是 O(1)但每个节点分散在内存各处缓存命中率低常数因子很大。所以在真实的工程里除非插入删除极其频繁否则数组往往是更好的默认选择。2.3 冒泡、插入、选择为什么必须亲手写一遍有人会问这三种排序又慢又没实际用途为什么还要写我的答案是它们是最好的指针与下标训练器。冒泡的核心是相邻比较与交换写它能让你彻底搞清双重循环的边界。看下面这段void bubbleSort(vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 已经有序提前收工 } }那个swapped标记不是可有可无的装饰。它在数组本来就近乎有序时能把最好情况压到 O(n)。很多人背模板时把它丢了然后写出来的冒泡在任何输入下都是 O(n²)。插入排序比冒泡更值得练。它的思想是维护一个已排好序的前缀每次把新元素插到合适位置。关键在于它的复杂度对输入敏感近乎有序时接近 O(n)逆序时才是 O(n²)。这正是很多工程排序库在数据规模很小比如小于 16 个元素时切换到插入排序的原因——小数组下它的常数极小比快排还快。选择排序的价值在于它的交换次数最少只有 n-1 次。当元素本身很大比如结构体、交换成本很高时这个特性有意义。还有一个词必须在这一层吃透稳定性。稳定性指的是值相等的元素排序后相对顺序是否保持不变。冒泡和插入是稳定的只要比较用严格大于号选择排序不稳定因为远距离交换会打乱顺序。多关键字排序时稳定性直接决定正确性——比如先按姓名排、再按班级排如果第二轮排序不稳定第一轮的姓名顺序就白排了。3. 五到六层分治排序与二分查找的边界地狱3.1 归并排序第一次真正理解分治归并排序是很多人第一次接触分治这个词。它的逻辑很干净把数组一分为二两边分别排好再把两个有序数组合并成一个。void mergeSort(vectorint a, int l, int r, vectorint tmp) { if (l r) return; int mid l (r - l) / 2; mergeSort(a, l, mid, tmp); mergeSort(a, mid 1, r, tmp); int i l, j mid 1, k l; while (i mid j r) tmp[k] (a[i] a[j]) ? a[i] : a[j]; while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) a[p] tmp[p]; }这里有两个细节值得说。第一mid用l (r - l) / 2而不是(l r) / 2是为了防止 l 和 r 都很大时相加溢出。这个习惯从这一层开始就要养成后面二分查找里同样会用到。第二合并时判断用而不是这保证了稳定性——左边先走相等元素就保持了原有的先后顺序。归并排序的时间复杂度稳定在 O(n log n)代价是需要 O(n) 的额外空间。它的真正威力不在排序本身而在那个合并的过程可以被改造去解决别的问题。最经典的是统计逆序对在合并时如果右半边的元素先被取出说明它比左半边剩下的所有元素都小逆序对数量直接加上左半边剩余元素的个数。这个技巧非常实用值得单独花时间写一遍。3.2 快速排序为什么工程实现里反而更常用快排的平均复杂度也是 O(n log n)最坏是 O(n²)而且不稳定那为什么各大标准库的排序底层往往是快排的变体原因有两个。一是它的常数因子小原地分区不需要额外数组缓存局部性好。二是最坏情况可以通过随机化主元规避——随机选一个元素和末尾交换再拿它做基准这样对手就没办法构造出针对性的最坏输入了。int partition(vectorint a, int l, int r) { int idx l rand() % (r - l 1); swap(a[idx], a[r]); int pivot a[r], i l; for (int j l; j r; j) if (a[j] pivot) swap(a[i], a[j]); swap(a[i], a[r]); return i; }这段分区逻辑里i始终指向小于基准区域的下一个空位。这种用指针划分区域的写法是后面双指针技巧的雏形练熟了对八层帮助很大。工程实现还有两个常见优化一是小数组通常阈值为 8 到 16切换插入排序减少递归开销二是三路划分把数组分成小于、等于、大于基准三段。当数组中存在大量重复元素时三路划分能把性能从 O(n²) 救回 O(n log n)这一点在处理成绩、年龄这类取值集中的数据时特别明显。3.3 堆与堆排序把随时拿到最值变成 O(log n)堆是个被低估的结构。很多人只在学堆排序时见过它之后就用priority_queue了其实理解堆的调整过程更重要。堆的本质是一棵完全二叉树用数组存储。下标为 i 的节点左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。大顶堆的性质是父节点不小于孩子。插入时把新元素放到末尾然后向上调整弹出堆顶时把末尾元素换到根再向下调整两者都是 O(log n)。priority_queueint, vectorint, greaterint pq; // 小顶堆 for (int x : nums) { pq.push(x); if (pq.size() k) pq.pop(); // 保持堆大小为 k } // 此时 pq.top() 就是第 k 大的元素这是求 TopK 的标准做法复杂度 O(n log k)比全排序的 O(n log n) 更优尤其在 n 很大 k 很小时优势明显。堆排序本身则是把建堆和反复取堆顶结合起来原地完成最坏也是 O(n log n)缺点是跳跃访问导致缓存不友好实际速度通常不如快排。3.4 二分查找写对边界比写对逻辑难得多二分查找的逻辑一句话说得完但它是初学者翻车率最高的地方没有之一。翻车点集中在三个地方中点溢出、区间开闭不一致、死循环。先说结论性的写法。我推荐统一使用左闭右开的区间[l, r)循环条件是l r这样所有情况都能自洽。// 找第一个 target 的下标即 lower_bound int lowerBound(const vectorint a, int target) { int l 0, r a.size(); // 区间 [l, r) while (l r) { int mid l (r - l) / 2; // 防溢出 if (a[mid] target) l mid 1; else r mid; } return l; // l 也是 target 的插入位置 }死循环的根源通常是把r mid - 1和l mid混着用同时又没处理好循环条件导致区间长度不再缩小。判断方法很简单每次循环结束后区间长度必须严格变小。拿这个尺子去量任何死循环都能揪出来。二分还有一个经常被忽视的前提单调性。数组必须有序或者更广义地说问题的答案必须具有单调性——存在一个分界点一侧全满足条件另一侧全不满足。很多二分答案的题就是在利用这个广义性质比如求最小的最大载重、求最大的最小间距这类题的标志是最大化最小值或最小化最大值看到这种措辞就可以往二分答案上想。4. 七到九层哈希、双指针与前缀和的降维打击4.1 哈希表第一次正式用空间换时间从这一层开始你要开始习惯一种思维用额外的存储换取更快的查询。两数之和是最经典的例子。暴力解法是双重循环O(n²)用哈希表一遍扫描就能做到 O(n)unordered_mapint, int pos; for (int i 0; i nums.size(); i) { int need target - nums[i]; if (pos.count(need)) return {pos[need], i}; pos[nums[i]] i; }这段代码的精髓在于边扫边存——不是先把所有元素放进表而是每处理一个元素就查它需要的搭档有没有出现过。这个套路在四数相加、和为 K 的子数组等题里反复出现。关于哈希表有几个细节值得记住。第一unordered_map的期望查询是 O(1)但最坏情况会退化到 O(n)因为所有元素可能落到同一个桶里。第二如果题目要求输出有序结果或者数据本身有序用map反而更合适它的底层是红黑树查询 O(log n) 但保证有序。第三在做性能敏感的题目时unordered_map的常数因子比数组大不少。如果键的范围很小比如字母、日期直接开定长数组当计数器速度会快好几倍这是写竞赛代码时的常用技巧。4.2 双指针与滑动窗口把 O(n²) 压成 O(n)双指针的精髓在于利用某种单调性让两个指针都只往一个方向走总移动次数不超过 2n。滑动窗口是双指针的一种特殊形式专门处理连续子数组/子串的问题。模板长这样int left 0, ans 0; unordered_mapchar, int cnt; for (int right 0; right s.size(); right) { cnt[s[right]]; // 右指针扩张 while (/* 窗口不合法 */) { cnt[s[left]]--; // 左指针收缩 if (cnt[s[left]] 0) cnt.erase(s[left]); left; } ans max(ans, right - left 1); }这个模板的结构必须刻进肌肉记忆外层 for 管右指针扩张内层 while 管左指针收缩收缩到窗口重新合法为止然后在收缩之后更新答案。为什么 while 不会把复杂度拖成 O(n²)因为左指针总共只会从 0 走到 n移动次数的总和是 O(n)摊到每次循环上是 O(1)。用这个模板做最长无重复字符子串、最小覆盖子串、长度最小的子数组会发现骨架完全一样只是合法的判定条件和答案的更新方式不同。把这一层吃透你会发现一大类题瞬间从困难变成填空。4.3 前缀和与差分区间问题的两把钥匙前缀和解决的是静态区间查询。定义pre[i]为前 i 个元素的和那么区间[l, r]的和就是pre[r1] - pre[l]O(1) 拿到答案。预处理是 O(n)之后每次查询都是 O(1)。vectorint pre(n 1, 0); for (int i 0; i n; i) pre[i 1] pre[i] a[i]; // 区间 [l, r] 的和 int sum pre[r 1] - pre[l];二维情况同理用容斥原理算块和公式是四角加减。这里最容易错的是下标偏移建议统一用pre[i1]对应a[i]并且下标从 1 开始算坑会少很多。差分是前缀和的逆运算解决的是多次区间加最后一次统一查询。它的思路是对区间[l, r]加 v只需要diff[l] v和diff[r1] - v最后对差分数组求一次前缀和就还原出了每个位置的实际增量。需求数据结构预处理单次操作多次区间查询前缀和O(n)O(1)多次区间修改差分O(n)O(1)修改查询交替树状数组/线段树O(n)O(log n)这个表最后一行是分界线。如果你发现修改和查询是交替出现的前缀和和差分都不够用了那就得进入线段树的世界——那是后话练气期先把前两行吃透。5. 第十层递归、分治与动态规划的第一道门槛5.1 递归写不对绝大多数时候是出口没想清楚递归的三要素是终止条件、本层逻辑、向下一层的递推。我观察下来出问题最多的永远是第一条。以反转链表为例递归写法只有几行但很多人盯着它看半天也想不明白ListNode* reverse(ListNode* head) { if (!head || !head-next) return head; // 出口 ListNode* newHead reverse(head-next); // 先翻转后面 head-next-next head; // 后一个节点指回自己 head-next nullptr; // 断开原来的指向 return newHead; }理解它的关键不是顺着代码往下想而是假设后面已经翻好了我这一层该做什么。这就是递归的思维方式相信子问题已经被解决只处理当前这一层的收尾工作。注意递归深度和栈空间直接相关。C 默认栈大小通常在几 MB 量级递归深度上万就很可能爆栈。数据规模大的时候要么改用迭代要么显式地自己维护一个栈。5.2 从记忆化搜索到递推DP 入门最稳的路径动态规划是很多人的心理阴影但入门的路径其实很清楚先写暴力递归发现重复子问题加上缓存变成记忆化搜索最后改写成递推。以爬楼梯为例。递归是f(n) f(n-1) f(n-2)直接写会指数爆炸因为f(3)、f(2)会被反复计算很多遍。加一个数组当缓存vectorint memo(n 1, -1); int f(int n) { if (n 2) return n; if (memo[n] ! -1) return memo[n]; return memo[n] f(n - 1) f(n - 2); }到这一步复杂度就从指数降到了 O(n)。再从后往前推就得到了递推写法空间还能进一步压缩到 O(1)int a 1, b 2; for (int i 3; i n; i) { int c a b; a b; b c; }我强烈建议所有人都按这个顺序走一遍不要一上来就抄递推公式。记忆化搜索能帮你保住状态定义这个最重要的直觉而状态定义错了递推公式写得再漂亮也是错的。判断一道题能不能用 DP看三个特征有最优子结构大问题的最优解由小问题的最优解拼出来、有重叠子问题不同路径会算到同一个状态、无后效性当前状态确定后未来只和当前有关和怎么来的无关。5.3 贪心的边界什么时候眼前最优真的成立贪心比 DP 简单但它的正确性需要用交换论证或归纳法去证明不能靠感觉。最经典的反例是硬币找零面额是 1、3、4要凑 6。贪心会先拿 4剩下 2 只能两个 1总共 3 枚而最优解是 3 3只要 2 枚。这说明这道题的贪心策略不成立得用 DP。反过来区间调度选最多不重叠的区间的贪心就是对的按结束时间排序能选就选。证明思路是最早结束的区间一定可以替换掉最优解里的第一个区间不会让结果变差。判断贪心能不能用的土办法先写个小规模暴力随机造几十组数据把贪心的结果和暴力的结果对比。全对再往大想有一组不对就立刻放弃贪心。这个验证习惯能帮你省下大量在错误策略上纠结的时间。6. 练气期最容易走火入魔的几个坑6.1 整数溢出与下标越界这两类错误在练气期出现的频率最高而且它们有个共同特点小数据测不出来一到大数据就暴毙。整数溢出最典型的场景是二分中点和哈希计算。(l r)在 l、r 都接近 2^31 时会溢出成负数所以必须写成l (r - l) / 2。另一个场景是求和n 个 10^9 级别的数相加很容易超过 int 上限这时候要提前换成 long long。下标越界的高发区是循环边界。i nums.size()是经典错误会在 i 等于 size 时越界。递归和分治里的mid 1、r - 1也容易飞出去。我的习惯是写完之后专门检查所有带下标的表达式把最小和最大情况代进去算一遍。6.2 死循环与递归爆栈死循环分两种。一种是显而易见的while(true)忘了退出条件。另一种更隐蔽藏在二分和双指针里区间没有收敛。检查方法前面提过——确认每次迭代区间长度严格减小。双指针里则要确认至少有一个指针在动并且两个指针都只往一个方向走。递归爆栈的排查反而不难加一行打印递归深度就能看出来。如果深度大得离谱说明出口条件写错了比如该用l r却写成了l r导致多递归一层。6.3 复杂度估错导致的超时超时是最让人沮丧的错误因为代码逻辑明明是对的。这时候先别改代码先算复杂度。数据规模 n可接受的复杂度常见误判10^3O(n²) 甚至 O(n³)无10^5O(n log n)把 O(n²) 当成了能过10^6O(n)用了排序或 map10^9O(log n) 或 O(1)想用数组开 10^9 直接爆内存一个特别容易踩的坑是明明用了unordered_map以为复杂度是 O(n)但常数太大10^6 规模就卡住了。这时候换成数组计数往往能立竿见影。7. 出了练气期之后筑基阶段该往哪走练气十层打通之后你会发现很多题已经能看出套路了。接下来的路我按经验给三个方向。7.1 树与图从 Prim 到最短路径图论是下一个大关卡起点是两件事图的存储邻接矩阵还是邻接表和图的遍历DFS 与 BFS。邻接矩阵适合稠密图查询两点是否相邻是 O(1)但开 n² 的空间邻接表适合稀疏图空间是 O(n m)遍历邻居更高效。再往下就是最小生成树和最短路径。Prim 算法从任意点开始每次把距离生成树最近的点拉进来适合稠密图配合优先队列可以优化最短路径里 Dijkstra 处理非负权Bellman-Ford 能处理负权并检测负环Floyd 一次算出所有点对的距离代码只有五行但复杂度是 O(n³)。这些算法的细节值得单独开一篇讲。7.2 字符串KMP 的思想内核KMP 的代码量不大但理解起来有门槛。它的核心是那个 next 数组也叫最长公共前后缀长度。为什么要有它因为在匹配失败时我们已经知道前面一段是匹配上的利用这个信息可以跳过那些不可能成功的起始位置把朴素匹配的 O(nm) 降到 O(nm)。理解 KMP 的关键是接受一个反直觉的事实模式串自己和自己匹配算出来的信息可以用来指导主串的匹配。把这一点想通了代码就好写了。7.3 别急着碰那些听起来很高级的算法最后说一个我见过最多的误区。刚入门的人听说模拟退火、蚁群、粒子群、遗传算法这些名字觉得高级就想直接上手。但这些东西是启发式算法没有正确性保证而且它们解决的是特定的优化问题日常刷题和工程里用得并不多。真正高频的仍然是那些基础结构数组、哈希、堆、二分、双指针、DP。等把基础打扎实了回头看那些高级算法你会发现它们的核心思想其实还是分治、贪心、状态空间搜索这些老朋友。带新人的时候我常做一件事让他在白纸上把十层对应的题各写一道限时不许查资料。写不出来的地方就是他真实的短板所在比刷一百道会做的题有价值得多。练气期最大的敌人从来不是题太难而是看起来会了。等到你能在没有任何参考的情况下把二分边界、滑动窗口收缩、递归出口这些细节一次性写对这一关才算真正过了。至于筑基之后的路那是另一个故事了。