最近几天在复试OJ上保持一个固定节奏：每天三道题，做完必须复盘。今天刚好轮到第4、5、6题，三道题分别涉及链表加法、回溯凑数、最长不重复子串，题型几乎没重叠，但都有一个共同点——代码看着不难，边界条件却特别容易写崩。这篇文章会把完整思路、参考代码和踩坑记录都整理出来，给也在准备复试机试的朋友一个参考。
1. 为什么坚持“每日3题”，以及这次复盘的整体思路
1.1 每天3题，刚好够形成“做完→复盘”的闭环
备考复试机试，最容易犯的错误就是贪多。我试过一天猛刷七八道题，结果第二天回头想，连当时的解题思路都串不起来。后来改成每天3题，效果反而好了很多。原因很简单：3道题的量刚好能覆盖两到三个高频考点，做完之后还能留出半小时写复盘笔记。如果再配合每周末把本周的题重新默写一遍，基本上能把“短期记忆”变成“条件反射”。
每天3题不是随便选的，我会提前把常见题型分成块：链表、树、DFS/回溯、BFS、动态规划、字符串、数学/模拟。每天从不同块里抽1道题，保证一周下来能覆盖八成以上的机试考点。这次的第4、5、6题就是按这个思路选的，正好串起了链表、回溯、字符串窗口三个方向。
1.2 复盘的核心不是抄代码，而是还原思考过程
我写复盘有个固定套路：先不看题解，自己把思路写一遍；然后对照代码，标注每个关键步骤“为什么这么写”；最后记录卡住的知识点。比如这次三道题，表面上是三类算法，实质上都指向同一个问题——你对自己的边界条件有没有把握。链表题要处理进位和空指针，回溯题要处理剪枝和重复组合，滑动窗口要处理左指针的回退。任何一个细节没想透，OJ就会用测试用例响亮地告诉你答案。
2. 第4题复盘：链表版两数相加
2.1 题目回顾与第一反应
题目很经典：两个非空链表分别代表两个非负整数，数字按逆序存储，也就是个位在链表头部。比如数字342，对应链表是2→4→3；数字465，对应链表是5→6→4。要求求两个数的和，结果也以逆序链表返回，所以342+465=807，结果应该是8→0→7。
我第一次看到这道题的反应是“这不就是把两个链表逐位相加吗”，结果一上手就被细节绊住了。最关键的是“进位”这个变量，它不像数组加法一样可以简单忽略。两个链表长度可能不一样，最后一位还可能产生额外进位。所有这些问题凑在一起，就需要一个统一的结构去处理。
2.2 建一个虚拟头节点，省掉一半特判
链表的插入操作最怕“头节点为空”的特殊情况。如果直接在返回的链表上操作，每次插入前都要判断“是不是第一个节点”。与其反复特判，不如在一开始就new一个dummy节点，之后cur指针永远指向当前尾节点，最后返回dummy->next。这是一个很通用的习惯：凡是需要“从零开始构建链表”的题目，都可以先建虚拟头节点，让后续逻辑变成无脑尾插。
注意dummy节点本身不存储有效数据，只是起到固定头节点的作用。这样做的好处是，无论循环里遇到什么分支，都不需要单独处理“空链表”“第一个元素”这种边界情况，代码的可读性也会高很多。
2.3 参考代码
struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode(0); ListNode* cur = dummy; int carry = 0; while (l1 || l2 || carry) { int sum = carry; if (l1) { sum += l1->val; l1 = l1->next; } if (l2) { sum += l2->val; l2 = l2->next; } cur->next = new ListNode(sum % 10); cur = cur->next; carry = sum / 10; } return dummy->next; }时间复杂度是O(max(m, n))，m和n分别是两个链表的长度。空间复杂度如果不算返回的链表，实际只有O(1)的临时变量。
2.4 我在这道题上实打实踩过的坑
第一个坑是循环条件。很多人只写while (l1 || l2)，这能覆盖两个链表都空的情况，却漏了两个链表都遍历完但carry还等于1的情况。比如5+5=10，结果是0→1，最后的1就是唯一一次多出来的进位。循环条件必须是while (l1 || l2 || carry)，否则最后一位carry会直接丢进虚空。
第二个坑是节点值的计算顺序。我一版代码写出了cur->next = new ListNode(sum)，也就是把sum整个作为节点值，结果5+5直接输出一个值为10的节点。正确做法是当前位存sum % 10，进位存sum / 10，这样节点值永远是0到9之间的数。
第三个坑是“复用节点”的诱惑。有人觉得可以把l1的节点拿来改值，省去new的空间开销。但复试OJ一般会复测原始链表，如果你修改了输入链表，可能导致后续判断出错。我建议所有结果节点都新建，不碰输入链表，这样最稳妥。
3. 第5题复盘：回溯 + 剪枝的经典组合题
3.1 题目回顾
题目给一个无重复数字的candidates数组，再给一个target，要求找出所有组合，使组合内数字之和等于target。关键条件是：candidates里的每个数字都可以无限重复使用。比如candidates = [2, 3, 6, 7]，target = 7，答案是[2, 2, 3]和[7]。
复试OJ里这道题的难点不是DFS本身，而是去重和剪枝。很多人能写出递归，但分支控制不好，结果就是输出一大堆重复组合。
3.2 思路展开：排序、递归传参、剪枝三者配合
回溯题的标准骨架是：递归函数里枚举当前可选择的下标，做出选择，递归进入下一层，撤销选择。但组合题有个特殊要求：组合是不看顺序的，[2,2,3]和[2,3,2]算同一个答案。为了去掉这种重复，递归时不能每次都从0开始枚举，而是从上一次选择的位置开始。因为每个数字可以重复取，所以递归时传入的起始下标不是i+1，而是i，表示当前位置还可以继续选。
排序在这道题里很关键。把candidates从小到大排序后，for循环里可以直接判断if (sum + candidates[i] > target) break。因为后面的数只会更大，一旦当前数加起来已经超过target，后面就不用再看了。这个剪枝能把很多无效递归直接砍掉，复试OJ时间紧的时候非常有用。
3.3 参考代码
class Solution { public: vector<vector<int>> res; vector<int> path; void dfs(vector<int>& candidates, int target, int sum, int startIndex) { if (sum == target) { res.push_back(path); return; } for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) { path.push_back(candidates[i]); dfs(candidates, target, sum + candidates[i], i); path.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); dfs(candidates, target, 0, 0); return res; } };时间复杂度难以精确计算，取决于组合数量，但排序+剪枝之后，实际递归分支会少很多。空间复杂度主要是递归栈深度，最坏是target/min(candidates)这个量级。
3.4 回溯去重：为什么不能“从0开始”
我在这道题被罚时过。第一次写的时候，递归函数是dfs(candidates, target, sum)，每次都从下标0开始枚举。结果就是题目示例明明只需要两个答案，我输出了[2,2,3]、[2,3,2]、[3,2,2]三个“看起来合法”的组合。OJ一看，答案错误。
原因并不复杂：从0开始枚举，等于把同一个组合的所有排列都找了一遍。组合问题要从startIndex开始，并且根据“能否重复使用当前元素”决定递归时传i还是i+1。可以重复使用就传i；每个元素只能用一次就传i+1。这个区别，是回溯题里最常考也最容易混的点。
还有个细节是递归栈里的终止条件。我因为先做了排序+循环内剪枝，所以递归开头不需要再写if (sum > target) return。但如果你没排序，就一定要在进入递归时判断sum > target，否则会导致无限制递归，程序超时甚至栈溢出。我建议复试阶段统一养成“排序后剪枝”的习惯，代码更短，思路也更清晰。
4. 第6题复盘：滑动窗口解最长不重复子串
4.1 题目回顾
给定一个字符串s，找出其中不含有重复字符的最长子串的长度。示例：“abcabcbb”的答案是3，因为最长子串是“abc”；“pwwkew”的答案是3，因为最长子串是“wke”。
这道题是字符串板块的必练题。很多复试OI题目会把它包装成“字符种类有限”的变体，但底层还是滑动窗口。先掌握最基础的版本，后面才有扩展的空间。
4.2 滑动窗口不是暴力解，而是一次遍历
暴力的做法是枚举所有子串，逐个判断是否包含重复字符，时间复杂度至少O(n^2)甚至O(n^3)，在OJ上大概率超时。滑动窗口的核心是维护两个指针left和right，让窗口始终满足“不含重复字符”。right指针负责扩展窗口，每次纳入一个新字符；如果发现窗口内已经出现过这个字符，就移动left指针，直到窗口重新变得合法。
我这里用到一个数组last[128]来记录每个字符最近一次出现的位置，初始化为-1。当right扫描到字符s[right]时，如果上一次出现的位置大于等于left，说明这个字符在当前窗口内已经存在，需要把left跳到last[s[right]] + 1，也就是重复字符上一次出现位置的后一位。这个“跳”的动作，比逐步left++高效得多，而且逻辑也更清晰。
4.3 参考代码
class Solution { public: int lengthOfLongestSubstring(string s) { vector<int> last(128, -1); int left = 0, ans = 0; for (int right = 0; right < s.size(); right++) { if (last[s[right]] >= left) { left = last[s[right]] + 1; } last[s[right]] = right; ans = max(ans, right - left + 1); } return ans; } };时间复杂度O(n)，因为left和right都只向右移动；空间复杂度是O(1)，这里用了固定大小的128数组。
4.4 最隐蔽的一个坑：左指针不能回退
这个坑我第一次写的时候完全没意识到。看代码里的条件判断：只有当last[s[right]] >= left，才更新left。很多简化版代码直接写成left = last[s[right]] + 1，这会在特定输入下出错。
举一个具体例子：s = “abba”。第一步right=0，字符a，left从0变？last[a] = -1，所以不更新，last[a]=0，ans=1。第二步right=1，字符b，last[b] = -1，不更新，last[b]=1，ans=2。第三步right=2，字符b，last[b]=1 >= left(0)，所以left跳到2，last[b]=2，ans=max(2, 1)=2。此时窗口是“bb”？不对，left=2，right=2，窗口只有一个b，ans保持不变。第四步right=3，字符a，last[a]=0。如果直接写left = last[a] + 1，left会变成1，这样left从2回退到1，窗口变成下标1到3的“bba”，长度为3，显然是错的。加上if条件后，因为last[a]=0 < left=2，所以left不更新，窗口继续保持合法。
这个坑特别容易出现，因为last数组记录的是字符上一次出现的位置，但可能在当前窗口之外。滑动窗口的left只能向右移动，不能回退，这就是为什么要多加一个判断。
4.5 空串和单字符的边界
字符串s为空时，循环不会执行，ans保持0，直接返回0。单字符时，循环执行一次，ans变成1，返回1。这版代码天然处理了这两种情况。如果写成ans初始化为1，反而要额外判断字符串为空，所以推荐ans初始化为0。
5. 复盘过程中值得记录的通用经验
5.1 复试OJ的输入输出和本地调试技巧
很多复试OJ不像在线题库那样直接填函数，它需要你自己写完整程序，包括读入和输出。链表和树的题目尤其麻烦，输入格式可能是按行给的节点值，也可能是一整个序列化的字符串。我的建议是：本地提前封装好“输入解析”和“结果打印”的函数，用示例数据跑通后再提交。避免把时间浪费在调试输入输出格式上。
另外，复试OJ的编译器版本往往偏保守。像C++17的结构化绑定、某些STL的写法，在老版本编译器上可能编译不过。我会先确认OJ支持的C++标准，再决定代码里能不能用auto、emplace_back这些语法。为了稳妥，刷题时尽量用最基础的语法，比如显式写迭代器或下标访问。
5.2 每次提交前过一遍“边界用例清单”
我吃过太多次“样例过了但提交不过”的亏，后来养成了固定的检查习惯：先看空输入，再看单元素输入，接着看全相同元素输入，然后看最大值溢出的场景，最后确认输出顺序。比如链表题一定要检查空链表和最后进位，回溯题要检查target比所有数都小的情况，滑动窗口要检查空串。
这个清单不用很长，但每次提交前花30秒过一遍，能省下大量罚时。复试OJ的罚时机制很真实，交错一次往往比多思考几分钟更打击心态。宁可提交前慢一点，也不要带着低级漏洞上去踩雷。
5.3 复盘笔记到底记什么最有用
很多人的复盘笔记就是抄一遍官方代码，然后贴个“AC”标签。我觉得那样意义不大。我自己的复盘模板是四个问题：
- 这道题考的是什么类型，对应哪种解题框架？
- 我第一反应想到的思路是什么，和正确解法的差异在哪？
- 卡住的那一步，是因为知识盲区，还是因为边界条件没想清楚？
- 有没有同类题可以一起归类？
把这三题按照模板写完后，我发现自己最常犯的错误集中在“循环终止条件”和“指针/索引更新时机”上。这种规律性总结，比刷十道新题更有价值，因为它直接指导了你下一阶段该练什么。
5.4 第4~6题的核心记忆点
很多朋友看完文章可能记不住三道题的完整代码，这很正常。我复盘的时候会把每道题压缩成一到两句话：
第4题链表加法：循环条件写成l1 || l2 || carry，当前位存sum % 10，进位存sum / 10，结果节点全部新建。
第5题组合总和：先排序，递归传i表示当前数字可重复使用，for循环里用sum + candidates[i] <= target剪枝。
第6题最长不重复子串：用last数组记录字符最近出现位置，只有当last[s[right]] >= left时才更新left，左指针永远不回退。
这三句话是我现在对这三道题的“最小记忆包”，每次复习先看这三句，再看自己的复盘笔记，就能快速把完整思路拉起来。
最后分享一个小习惯：每次刷完一组合适的题，我会把这三道题放进一个“周复习”队列，周末找个时间不看任何提示，直接在OJ上重新提交一次。如果一道题能连续两次无提示AC，才算真正过关。这个方法帮我避开了“当时看懂，两周后全忘”的无效刷题陷阱。复试准备本来就是一场和自己较劲的过程，练得多不如练得准，练得准还得记得牢。
