前阵子有个刚转方向的朋友找我聊天，说他刷了将近两百道题，可一遇到没见过的题型还是发懵，写完的代码不是超时就是边界出错。我让他随手写个二分查找，他憋了半天，写出了三个版本，一个死循环，一个漏掉了最后一个元素，还有一个在数组为空时直接崩掉。问题不在他不够努力，而在于他把算法当成了一堆彼此独立的"知识点"去背，而不是当成一套需要逐层打磨的能力去练。

这篇文章我想聊的，就是我这些年带人、也带自己走过来的一条入门路径。我把它戏称为算法修炼之练气篇，而"练气十层"指的是入门阶段需要打通的十个能力台阶。这套划分不按教材章节走，而是按"你能独立写出什么"来定层。它适合刚接触数据结构和算法的人，也适合刷了题但总觉得地基不牢的人。看完之后，你至少能清楚地知道自己现在卡在第几层，以及上一层需要补什么。

1. 把算法入门拆成"十层"：这套划分到底怎么来的

1.1 为什么按"层"排，而不是按"知识点"排

教材的组织方式是按知识块来的：数组、链表、栈、队列、树、图、排序、查找，一块一块往下讲。这种方式适合系统学习，但有个副作用——它让人误以为这些块是平的，学完数组就等于和学完图站在同一水平线上。实际不是。能力的成长是立体的，有些东西你没打通，后面所有的东西都会变形。

我举个很常见的例子。有人能背出归并排序的模板，但你让他解释为什么要额外开一个数组、为什么它稳定而快排不稳定，他答不上来。这说明他停在了"抄写"层，没到"理解"层。再比如，有人会用unordered_map做两数之和，但一旦数据范围变成 10^9、内存吃紧，他就不知道换什么结构了，因为他从来没想过哈希表是在拿什么换什么。

按"层"排的好处是，每一层都有一个明确的能力标志：不是"我知道这个东西"，而是"我能在不看模板的情况下，写出边界正确、复杂度达标、还能说清为什么这样写的代码"。这个标准说起来简单，卡住的人一大片。

1.2 练气十层的具体划分与自测方法

下面这张表是我自己用的分法。层数不是严格的先后顺序，前一层没稳，后一层也能学，但会一直返工。

自测的方法很土但有效：找一张白纸，把每一层对应的经典题写一遍，不看任何资料，写完自己造三组数据——最小规模、最大规模、边界（空、单元素、全相同）。能全过，这层就算过了；只要有一组崩，就老老实实回头补。

提示：自测时不要用在线判题，直接用白纸或者纯文本编辑器。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)。删除同理。

最后一行经常被忽略，但它很关键。数组的连续内存能吃到 CPU 缓存的红利，实际跑起来比理论复杂度看起来的还要快。链表虽然理论上删除是 O(1)，但每个节点分散在内存各处，缓存命中率低，常数因子很大。所以在真实的工程里，除非插入删除极其频繁，否则数组往往是更好的默认选择。

2.3 冒泡、插入、选择：为什么必须亲手写一遍

有人会问，这三种排序又慢又没实际用途，为什么还要写？我的答案是：它们是最好的"指针与下标训练器"。

冒泡的核心是相邻比较与交换，写它能让你彻底搞清双重循环的边界。看下面这段：

void bubbleSort(vector<int>& 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(vector<int>& a, int l, int r, vector<int>& 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(vector<int>& 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 的节点，左孩子是 2i+1，右孩子是 2i+2，父节点是 (i-1)/2。大顶堆的性质是父节点不小于孩子。插入时把新元素放到末尾然后向上调整，弹出堆顶时把末尾元素换到根再向下调整，两者都是 O(log n)。

priority_queue<int, vector<int>, greater<int>> 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 vector<int>& 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_map<int, 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_map<char, 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[r+1] - pre[l]，O(1) 拿到答案。预处理是 O(n)，之后每次查询都是 O(1)。

vector<int> 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[i+1]对应a[i]，并且下标从 1 开始算，坑会少很多。

差分是前缀和的逆运算，解决的是"多次区间加，最后一次统一查询"。它的思路是：对区间[l, r]加 v，只需要diff[l] += v和diff[r+1] -= v，最后对差分数组求一次前缀和，就还原出了每个位置的实际增量。

这个表最后一行是分界线。如果你发现修改和查询是交替出现的，前缀和和差分都不够用了，那就得进入线段树的世界——那是后话，练气期先把前两行吃透。

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)会被反复计算很多遍。加一个数组当缓存：

vector<int> 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 复杂度估错导致的超时

超时是最让人沮丧的错误，因为代码逻辑明明是对的。这时候先别改代码，先算复杂度。

一个特别容易踩的坑是：明明用了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(n+m)。

理解 KMP 的关键是接受一个反直觉的事实：模式串自己和自己匹配，算出来的信息可以用来指导主串的匹配。把这一点想通了，代码就好写了。

7.3 别急着碰那些听起来很高级的算法

最后说一个我见过最多的误区。刚入门的人听说模拟退火、蚁群、粒子群、遗传算法这些名字，觉得高级，就想直接上手。但这些东西是启发式算法，没有正确性保证，而且它们解决的是特定的优化问题，日常刷题和工程里用得并不多。真正高频的仍然是那些基础结构：数组、哈希、堆、二分、双指针、DP。

等把基础打扎实了，回头看那些"高级算法"，你会发现它们的核心思想其实还是分治、贪心、状态空间搜索这些老朋友。

带新人的时候我常做一件事：让他在白纸上把十层对应的题各写一道，限时，不许查资料。写不出来的地方就是他真实的短板所在，比刷一百道会做的题有价值得多。练气期最大的敌人从来不是题太难，而是"看起来会了"。等到你能在没有任何参考的情况下，把二分边界、滑动窗口收缩、递归出口这些细节一次性写对，这一关才算真正过了。至于筑基之后的路，那是另一个故事了。