1. 这份笔记从哪来，适合谁看
把标题拆开看就一句话：这是一个C++入门选手写给自己的算法刷题笔记。不是什么系统教材，也不是什么大神心得，就是我自己边学边记录、边踩坑边修正的东西，顺手整理出来分享给同样在摸索的人。
先说说我自己的情况，方便你判断内容适不适合你。我写C++写过一阵子业务代码，但算法这块一直是短板，做题基本靠直觉，碰上稍复杂的就抓瞎。今年决定系统地补一补，把力扣、洛谷、牛客上的题按专题刷，边刷边把套路记下来。这份笔记就是那时候开始攒的，到现在已经积累了小两百条，还在持续更新。
笔记主要解决三个问题。第一是知识碎片化——今天学个链表、明天碰个DP，过两周全忘了，必须有个地方把套路固定下来。第二是代码模板化——很多算法本质上就是几套固定写法的变种，把模板记熟，能省掉大量重复推导时间。第三是排错经验化——算法题里最耗时间的其实是各种隐蔽错误，比如数组越界、死循环、边界条件，这些坑光靠看书学不到，必须自己踩一遍才能记住。
所以这份笔记的核心价值不在于"系统全面"，而在于**"实战可复现"**——每条笔记都对应一个真实题目或真实场景，写的时候就能直接用。笔记默认你有基本语法功底（知道指针、引用、STL容器是什么），但不需要你有算法竞赛背景，零基础刷题的人跟着这个框架走完全没问题。
我用的编译器是GCC 9.4，配合VS Code环境，刷题平台是力扣和洛谷。后面所有代码都基于C++11标准，个别地方用了C++17的特性我会单独标注。
2. 整体设计思路：为什么我选择"专题刷题+模板沉淀"的方式
2.1 入门算法的核心矛盾：知识量大与时间精力有限的冲突
算法题涉及的知识点非常多：数组、链表、栈、队列、树、图、排序、搜索、动态规划、贪心、回溯、字符串匹配……如果按教材一章一章啃，啃到树就已经想放弃了。但反过来看，真正笔试面试常考的并没那么玄乎，核心其实就是那几个固定专题的排列组合。
我统计过自己刷的一百多道题，出题频率最高的就这几类：双指针和滑动窗口大概占20%，二分查找和二分答案差不多15%，数据结构设计题15%，DFS和BFS搜索15%，动态规划15%，剩下是贪心、回溯和杂题。这个比例说明一件事：你把六七个专题的套路吃透，就能覆盖八成以上的题目。这就是我选择专题刷题而不是按页翻书的原因。
2.2 模板沉淀：一篇笔记解决一类题
一个很深的体会是：一道题你会做不代表你掌握了这一类题。很多题看起来不一样，底层解法是同一套东西。比如"最长无重复子串"、"最小覆盖子串"、"长度最小的子数组"，表面上三题完全无关，但全部可以用滑动窗口模板解决。我笔记里的做法就是，刷完一类题之后立刻总结一版"通用解法模板"，配合两三道典型例题，之后遇到同类型的题目直接套模板改参数，效率比每次从头推导高太多。
2.3 笔记结构的演进：从流水账到反查手册
最早我的笔记就是流水账——今天刷了什么题、AC还是WA、用了什么方法，写到后面发现根本没法查。后来我重构了一次，按专题分类组织，每条笔记包含五个要素：问题模型、核心思路、代码模板、复杂度分析、易错点。现在做题遇到卡壳，我能快速定位到相关笔记，比搜索引擎还好用。
这个结构这里也分享给你，后面每个专题我都是按这五个要素来写的。
3. 核心知识点拆解：STL容器到底该怎么用
3.1 vector的底层机制与性能取舍
vector是C++里用得最多的容器，但很多人只是当"可变长数组"用，对它的底层机制和性能特性了解不够。
vector的本质是动态数组，底层维护三个指针：起始位置、当前使用末尾、容量末尾。当元素数量超过当前容量时，vector会重新分配一块更大的内存（通常翻倍），把旧元素逐个拷贝过去，然后释放旧内存。这一步非常贵——如果你在循环里不断push_back，触发了扩容，时间复杂度就是O(n)的拷贝开销。
实操中我的建议：如果能预估元素数量上限，直接调用reserve预留空间。举个例子，你要读取一个有N个整数的数组：
int n; cin >> n; vector<int> nums; nums.reserve(n); // 推荐，避免多次扩容拷贝 for (int i = 0; i < n; i++) { int x; cin >> x; nums.push_back(x); }顺便说一个刷题时经常踩的坑：vector的size()返回的是size_t类型（无符号整数），如果直接拿0去减它，得到的是一个巨大的正数，导致循环永远不结束或者越界。正确写法是先转成int再减，或者用nums.size()参与比较时保持两边同为无符号类型。
3.2 map、set与unordered系列的选择逻辑
很多新手纠结什么时候用map、什么时候用unordered_map，这里有个简单的判断标准：
- 需要有序遍历键值对：用map（底层红黑树，O(log n)操作）
- 只需要快速查找不需要顺序：用unordered_map（底层哈希表，平均O(1)操作）
- 需要判断元素是否存在且不关心顺序：用unordered_set
- 需要去重且保持顺序：用set
实际刷题时，九成以上的题目用unordered_map就够了，因为哈希查找的常数极小，性能远好于红黑树的log n。只有在考到"按顺序输出"或者"找第k小元素"这类需要区间操作时，才轮到map和set出场。
有个细节要注意：unordered_map的遍历顺序是不确定的，如果你的结果对顺序有要求，必须先排序再处理。
3.3 priority_queue与自定义比较器
优先队列（堆）是很多算法题的利器，特别是涉及"每次取最大/最小"的场景。默认的priority_queue是大顶堆，取的是最大元素。如果要取最小元素，一般两种写法：
// 写法一：用 greater 指定小顶堆 priority_queue<int, vector<int>, greater<int>> minHeap; // 写法二：存入负值 priority_queue<int> maxHeap; maxHeap.push(-x); // 取出来的时候记得取负对于自定义结构体，需要重载比较运算符。这里是重灾区，很多人搞不清比较方向和堆的大小的关系。我的记忆技巧是：返回true表示第一个参数排在第二个参数后面，也就是优先级更低。
struct Node { int dist; int id; }; // 自定义小顶堆：dist小的优先 struct Cmp { bool operator()(const Node& a, const Node& b) { return a.dist > b.dist; // 注意：小顶堆用的是大于号 } }; priority_queue<Node, vector<Node>, Cmp> pq;提示：Dijkstra算法、合并K个有序链表、滑动窗口最大值这些经典问题，底层全依赖优先队列，这个容器值得花一小时专门练透。
3.4 string的常用操作与坑
字符串在算法题里绕不开，尤其是处理子串、回文串、字符统计。C++的string有不少方便的函数，但有几个坑值得注意：
- substr的参数是"起始位置，长度"，不是"起始位置，结束位置"。很多从Python转过来的人容易在这上面翻车。
- getline配合cin处理含空格的整行输入：如果你前面用过
cin >>，缓冲区会留下换行符，直接用getline会读到空行。解决办法是先cin.ignore()。 - 字符统计用数组代替map：如果范围是26个小写字母，直接用
vector<int> cnt(26, 0)，性能远好于unordered_map。这是一个经常被忽视的优化点。 - 对string做大量拼接操作时，注意
+=比str = str + ch高效得多，前者是原地操作，后者会创建新对象。
4. 经典算法模板与场景拆解
4.1 二分查找：不是"找到"就完了，而是"边界"
二分查找算得上最"简单"也最容易写错的算法。说它简单是因为思路就一句话——每次砍掉一半，说它容易写错是因为边界条件稍微调错就是死循环或者漏解。
我推荐的写法是左闭右开区间，配合searchFirst等价变体统一处理，这样记起来只有一个模板：
// 在有序数组中查找第一个 >= target 的元素位置（不存在返回 nums.size()） int lower_bound(vector<int>& nums, int target) { int left = 0, right = nums.size(); // 左闭右开 while (left < right) { int mid = left + (right - left) / 2; // 防溢出写法 if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; }注意我用了left + (right - left) / 2而不是(left + right) / 2。当left和right都接近2^31时，直接相加可能溢出。虽然在普通题目里不容易触发，但这是个好习惯，竞赛时能救你一命。
这套模板的核心思想：始终保持"答案可能在[left, right)"区间内"，最终left和right会收敛到同一个位置，这个位置就是答案。想找"最后一个小于target的元素"就得在判断条件上做文章，但区间框架不变。
4.2 滑动窗口：最长与最短的套路差异
滑动窗口是双指针思想的进阶版，专门用于处理子数组/子串问题。核心维护一个窗口[left, right]，通过扩展和收缩遍历所有可能的状态。
最长类问题（如无重复最长子串）的模板：
int maxWindow(vector<int>& nums) { int left = 0, ans = 0; unordered_map<int, int> window; // 记录窗口内元素状态 for (int right = 0; right < nums.size(); right++) { window[nums[right]]++; while (窗口条件不满足) { // 收缩左边界 window[nums[left]]--; if (window[nums[left]] == 0) window.erase(nums[left]); left++; } ans = max(ans, right - left + 1); } return ans; }最短类问题（如最短覆盖子串）则是完全相反的形态——先不断扩展直到满足条件，再尝试收缩找最短。这两者的核心区别在于：最长类窗口是"不满足才收缩"，最短类窗口是"满足就收缩"。我一开始把这两套逻辑混在一起，每次写都要推半天，后来把模板分开记录之后，基本秒套。
有一个高频考点是窗口内的统计方式。如果只涉及字符且字符范围有限（比如只有字母），建议用数组计数而不是map，代码如下：
vector<int> cnt(128, 0); // ASCII码范围 int needCnt = 0; // 记录满足条件的字符种类数4.3 DFS与BFS：搜迷宫和求最短路的两种武器
搜索是算法题的分水岭。DFS（深度优先搜索）适合"求所有解"的场景：全排列、组合、岛屿数量、回溯剪枝；BFS（广度优先搜索）适合"求最短路径"的场景：走迷宫、最小步数、单词接龙。
DFS的经典框架（以岛屿数量为例）：
void dfs(vector<vector<char>>& grid, int i, int j) { if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) return; if (grid[i][j] == '0') return; // 已访问或非陆地 grid[i][j] = '0'; // 标记已访问（原地修改） dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1); }这里有个非常关键的点：visited标记一定要在递归进入之前完成。如果放在递归开始之后，可能会造成重复访问和死循环。我一开始习惯性在进入下一层之前不加标记，超时之后排查半天才发现问题。
BFS框架则依赖队列：
int bfs(vector<vector<int>>& grid, int startX, int startY) { int n = grid.size(), m = grid[0].size(); vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; q.push({startX, startY}); dist[startX][startY] = 0; int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (auto& d : dirs) { int nx = x + d[0], ny = y + d[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } return dist[目标x][目标y]; }用dist数组同时承担"是否访问过"和"距离为多少"两个职责，这是BFS中最常用的优化写法，能省一个额外的visited数组。
4.4 动态规划：入门最难啃但回报最大的一章
动态规划是很多人的噩梦，我一开始也被吓到，后来发现其实是方法论问题。比起背状态转移方程，更重要的是按固定步骤思考：
- 定义状态：dp[i]表示什么？大多数题目里dp[i]代表"以第i个元素结尾的最优解"或者"前i个元素的最优解"。
- 写出转移方程：dp[i]怎么由更小的状态推出来？
- 确定初始条件：dp[0]或dp[1]等于什么？
- 确认遍历顺序：从前往后还是从后往前？一维还是二维？
以最经典的最长递增子序列（LIS）为例：
int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> dp(n, 1); // 初始值：每个元素自身构成长度为1的序列 int ans = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } return ans; }这个O(n²)的写法是最容易理解的版本。如果想优化到O(n log n)，需要用贪心+二分维护一个"递增序列的尾部最小值"数组，这个进阶版本我放在笔记后面作为拓展题，不建议新手一上来就啃。
DP的题感培养需要大量题量支撑。我个人经验是：先保证能把"背包问题、最长公共子序列、最长递增子序列、编辑距离"这四个最经典模型吃透，之后再看其他DP题就不会觉得是完全陌生的了。
5. 精度、溢出与性能调优：算法题里最隐蔽的坑
5.1 整数溢出的常见场景
C++刷题最常见的问题之一就是溢出。比如计算中间值时两个10^9的数相乘，直接得到10^18，已经超过int上限（约2.1×10^9）。很多人题目思路全对，提交却WA，一查才发现是溢出。
我的检查清单：
- 运算过程中涉及乘法，且数值可能超过10^4，先把变量类型设成
long long - 求平均值取
(left + right) / 2时，用left + (right - left) / 2防溢出 - 状态转移方程里出现加法，比如二维DP中
dp[i][j] + dp[i][j-1]，如果答案可能超过int上限，dp数组直接定义成vector<vector<long long>>
5.2 浮点数比较：永远不要用==
如果你做过涉及浮点数的题，比如二分答案求平方根，一定会遇到精度问题。浮点数在内存中是近似表示的，所以sqrt(2) * sqrt(2) == 2在C++里很可能得到false。
正确的做法是定义一个极小值epsilon，用绝对值差是否小于epsilon来判断。
const double EPS = 1e-8; if (fabs(a - b) < EPS) { // 视为相等 }5.3 时间复杂度的估算方法
很多新手问我，题目提交超时是不是算法不够好。实际上超时有两个原因：要么复杂度太高，要么常数太大。前者靠换算法，后者靠优化编码细节。
估算方法很简单：假设你的程序每秒能执行大约10^8次基本运算（这个值对OJ环境大致适用）。那么：
- 数据规模n = 10^5，O(n²)算法 = 10^10次，必超时
- 数据规模n = 10^5，O(n log n)算法 ≈ 1.7×10^6次，很安全
- 数据规模n = 10^6，O(n)算法 = 10^6次，没问题
拿到题目第一件事不是写代码，而是先看数据范围确定允许的复杂度级别。这个习惯能帮你排除掉一半的错误思路。比如看到n ≤ 10^5，就应该立刻排除需要两层循环的O(n²)解法。
5.4 输入输出优化：cin和cout没你想的那么慢
刷题时经常听到"用scanf，别用cin"的说法。这个说法有历史背景：早期C++的cin为了兼容C的stdio，默认开启了同步，导致性能偏低。但在现代OJ上，你只要在main开头加上一行：
ios::sync_with_stdio(false); cin.tie(nullptr);cin和cout的速度就能逼近scanf/printf，完全够用。我个人是能用cin就用cin，省去格式串的调试时间，只有需要格式化输出特定宽度时才用printf。
这行的原理是关闭C和C++两套IO的同步缓冲区，cin和cout不再等待stdio的刷新，自然就快了。注意关闭同步后，不要混用cin和scanf（会乱序），这点写在笔记的第一页。
6. 常见问题与排查技巧实录
6.1 编译错误篇：大多数人卡住的不是算法
我能说一半以上新手提交不通过，卡在编译错误阶段吗？常见的编译错误有这几种：
- 忘了引入头文件：用
vector不加<vector>，用sqrt不加<cmath>。解决办法是养成"写完代码先自查include"的习惯。 - 结构体比较没重载运算符：用了sort对自定义结构体排序，却忘了定义比较函数，编译直接报错。
- 函数声明和定义不匹配：特别是模板函数，声明时用了
T，定义时用了int，类型对不上。 - 注意C++11起的特性差异：
auto、unordered_map、make_pair这些都是C++11的，如果平台用的是C++98标准，全部报错。刷题前先确认标准版本。
一个非常实用的排错技巧：从报错信息的最后一行倒着看。编译器的报错经常是级联的——第一个错误引发后面几十个错误，但真正的源头往往在最后那一行。
6.2 运行时错误：段错误和栈溢出的区别
提交后报Runtime Error，大多数情况是段错误（访问了非法内存）。常见的触发点：
- 数组越界：
vector<int> nums(10); nums[10] = 1;下标最大只能是9 - 空指针/野指针：用了一个未初始化的指针
- 解引用end迭代器：
*nums.end()是未定义行为 - 递归深度过大：DFS递归穿过1万层以上可能爆栈
如果是递归爆栈，有两个解决办法：一是把递归改成显式的栈模拟，比如用stack保存状态；二是把DFS改成BFS。设计算法时就考虑递归深度，比出了问题再改要省事得多。
6.3 逻辑错误：AC代码为什么总差一点点
最气人的是"本地运行没问题，提交就WA"。这类问题绝大多数是边界条件没处理好：
- 空数组、只含一个元素的数组
- 已经有序的数组
- 全是相同元素的数组
- 最大值的边界情况（比如k大于数组长度）
我的建议是写完代码后，走一遍自己写的样例还不够，要手动构造3-4个极端用例。比如排序算法测一下[]和[5]，二分查找测一下target小于所有元素和target大于所有元素的情况。五毛钱的功夫，能省去半天调试时间。
6.4 死循环的排查套路
如果你发现程序卡住不输出，多半是循环没退出。排查顺序：
- 二分查找的left和right更新是否正确：
left = mid + 1和right = mid这是正确节奏，如果把left = mid就会陷入两个相邻位置的死循环 - 滑动窗口的left是否在某个条件下永不右移
- 链表的快慢指针有没有在同一节点打转
- DFS/BFS的状态标记是否漏了某个分支
有一个调试技巧很实用——在循环体的开头加一行cout << "debug: " << left << " " << right << endl;，观察变量变化，死循环的位置立刻暴露。用完记得删掉。
7. 环境配置与刷题工作流
7.1 本地调试环境搭建要点
虽然OJ上提交不看本地环境，但本地调试能极大提升刷题效率。我的开发环境是三件套：VSCode + GCC + 一个简单的测试脚本。
写算法题时，我从来不在一个main函数里堆代码——而是写一个包含全部测试用例的单文件测试，用命令行编译运行：
g++ -std=c++17 -Wall -Wextra -g -o main main.cpp-Wall -Wextra能提示绝大多数未定义行为和类型转换问题，-g生成调试信息配合gdb使用。这些编译选项在OJ上是不会启用的，所以在本地编译干净通过，能提前过滤掉一大半问题。
7.2 刷题前5分钟的准备动作
我每次开始刷题前，会先花五分钟默一遍基础模板：快排的partition、二分查找的两个变体、DFS和BFS的骨架、滑动窗口的左右指针移动逻辑。这就像热身，能让手和大脑快速进入状态。
如果你还没有自己整理过模板，我的建议是现在就打开一个空白文档，手敲一遍上面列的核心模板。手敲和复制粘贴的差别很大——敲的过程中你才会注意到那些边界条件的细节。
7.3 笔记更新的迭代方式
这份笔记写了小半年，更新方式从一开始的"刷到哪记到哪"变成了现在的版本管理方式：每个专题单独一个文件，每次刷题后如果有新感悟或者新坑，追加在对应专题的"补充记录"区域。我现在习惯在每道题提交通过之后，顺手更新笔记——哪怕只是加一条"这题可以用上一题模板直接套"。这样积累足够多之后，笔记就是一本完全个人化的算法手册。
8. 最后的实操建议
8.1 做题顺序怎么定：先广度后深度
如果你刚开始刷题，我强烈建议按这个顺序扫一遍知识点：线性表（数组、链表、栈、队列）→ 哈希表 → 排序与自定义排序 → 二分查找 → 双指针/滑动窗口 → 树的基础遍历 → DFS/BFS → 回溯 → 贪心 → 动态规划。
前段是性价比最高的内容，投入三四周就能有明显感觉。动态规划放到最后不是因为不重要，而是因为它需要综合运用前面的数据结构基础，太早接触容易打击信心。
8.2 一道题刷到什么程度算"会了"
我自己的标准有三层：能独立AC、能讲清楚思路和复杂度、能说出这题的变种以及模板还有哪些其他用途。只满足第一层算"做过了"，三层都满足才算"掌握了"。后者关系到你碰到新题时能不能快速联想到旧套路。
每道题AC之后，建议顺手做两件事：一是看一眼题解区是否有比你的方法更优的解法，记录下来；二是想一想如果题目稍微改一下条件（比如数组变成无序、最大值改为最小值、m次改为k次），你的解法还成立吗。这两个习惯对培养算法思维特别有效。
8.3 分享我的一个习惯：错题本比题单更值钱
我做题最宝贵的资产不是AC过的题，而是那些多次提交才过、或者看了题解才恍然大悟的题。遇到这种题，我除了正常笔记外，专门在文档末尾加了一个"弱题清单"，记录当时的卡壳点。每周回头重做清单里的题，直到一次AC再移出清单。这比每天刷新题有效得多——你真正需要训练的是你的薄弱点，而不是你已经会的东西。
这份笔记还在持续更新，接下来我会补充的内容包括：图论进阶（拓扑排序、并查集、最短路）、字符串算法（KMP、Trie树）、更多动态规划的经典模型，以及一些竞赛向的技巧。如果你是按这篇笔记的框架来学习的，建议每学完一个专题写自己的三条总结，把你遇到的坑和心得也记进去——自己的笔记永远是最好用的笔记。
