2026-03-15周日算法打卡第23天。今天准备了一份“组合拳”题单双指针、链表、回溯算法三个专题共6道题。这6道题不是随便凑的练完之后你会发现一个很有意思的事实——这三个看似独立的专题底层的思维方式其实是一套东西穷举所有的可能性再用约束条件把没必要的分支砍掉。双指针是砍掉有序序列里的无效比较链表操作是小心翼翼地改引用关系回溯则是走迷宫式的“试一步、退一步”。这套题单适合几类人准备面试、想系统巩固基础算法、或者参加蓝桥杯这类比赛的人。难度上从简单到中等都有不会上来就把人劝退但也绝没有白给的题每道题都有值得反复咀嚼的细节。这篇文章不只是给答案我会把每一题的思考过程、关键代码、易错点全部拆开讲一遍。1. 今日清单与训练思路1.1 为什么把这三个专题放在同一天我练算法有个习惯同一类题连续刷容易产生路径依赖今天做对了不代表真懂了可能只是记住了套路。所以我会把关联度高的专题交叉着来双指针、链表、回溯正好是三个经常在面试题里“串门”的考点。双指针解决的是有序或区间类问题核心是利用单调性减少枚举次数。链表是天然的指针操作练习场练的是对引用赋值的精准控制。回溯算法则是暴力枚举的高级形态它解决的是“在多个选择中搜索可行解”的问题。三个专题有一个共同点都需要你在大脑里维护一个清晰的状态。做个类比你就明白了。双指针像两个人站在一条线的两端根据条件一点点靠近谁该动、为什么动是解题关键。链表操作像在调整一列多米诺骨牌中间某几张的位置动之前必须想清楚谁指向谁顺序错了整条链就断了。回溯算法像在迷宫里走路每条路都试一步走不通就退回上一个岔路口换一条路。这三个专题同一天练等于把“维护状态、做出选择、撤销选择”这套思维模型练了三遍。后面做题你会发现好多难题其实就是这几个基础模型的组合。1.2 今日题目清单与难度对标今天的6道题我按专题归类也标了难度和核心考点方便你对照练习| 题目 | 专题 | 难度 | 核心考点 | | 三数之和 | 双指针 | 中等 | 排序 左右指针夹逼 去重 | | 盛最多水的容器 | 双指针 | 中等 | 贪心移动矮边证明移动正确性 | | 反转链表 | 链表 | 简单 | 迭代三指针 / 递归指针保存顺序 | | 环形链表 II | 链表 | 中等 | 快慢指针 环入口的数学推导 | | 全排列 | 回溯 | 中等 | visited标记 递归 状态撤销 | | 组合总和 | 回溯 | 中等 | 排序剪枝 startIndex控制 可重复取数 |这个组合在面试中出现频率极高。三数之和是双指针的“招牌题”盛水容器是同思路的变体反转链表几乎是链表题的“开胃菜”环形链表是快慢指针的进阶全排列是回溯的入门必做组合总和则加了排序剪枝的优化点。把这6道吃透很多中等难度的题你都会感觉“见过”。2. 双指针专题左右夹逼与快慢推进2.1 双指针的本质与两大范式双指针听起来高大上本质就是“在遍历过程中用两个下标代替一个下标减少重复计算”。它分为两大类一类是相向而行的左右指针通常用在有序数组或者需要比较两个端点的场景另一类是同向而行的快慢指针通常用在链表中找特定位置或判断是否有环的场景。左右指针的典型场景是在一段有序的数组里找两个数使得它们的和等于某个值。暴力做法是两层循环时间复杂度O(n²)。但如果数组有序你就可以用一个指针指最左一个指最右根据当前和的大小决定往哪边移动。为什么有序那么重要因为有序给了你一个单调性你知道左边小右边大和偏大就动右边和偏小就动左边每次移动都距离目标更近一步。快慢指针的典型场景是判断链表有没有环。慢指针每次走一步快指针每次走两步如果链表有环它们必然会在环里相遇。好比操场上两个人跑步速度快的迟早套圈追上速度慢的。这两个范式对应到这周的三数之和、盛水容器、环形链表三题你会发现核心其实就是一个移动规则的问题。2.2 三数之和的排序与去重细节三数之和要求在一个数组里找到所有三个数的组合使得它们的和为0并且结果不能包含重复三元组。很多人第一反应是三重循环但题目要求去重三重循环去重会写得非常痛苦复杂度也不对。正确做法是先排序然后固定第一个数i剩下两个数用左右指针在i后面这段区间里夹逼。排序的意义有两个一来是方便我们用和的大小来移动指针二来是让相同的数字聚在一起方便去重。这里最容易被坑的是去重的时机。我见过不少新手在收集到一组答案之后直接用while跳过重复元素这个没问题但容易写得粗糙导致越界。更常见的问题是在第一层循环里忘掉跳过重复的i。记住一个口诀外层i去重看nums[i]和nums[i-1]是否相等内层left/right去重要在找到一组解之后再做。还有一个小优化如果nums[i]本身已经大于0因为数组升序后面的数全都大于0直接break掉这是很自然的剪枝。2.3 盛最多水的容器为什么移动矮边这个题的经典场景是给你一堆高度每两个高度形成一条线段线段之间围出一个矩形区域矩形的宽是两个下标的距离高是两条线段中较矮的那条问能围出的最大面积是多少。最直接的思路是双重循环枚举所有组合O(n²)复杂度在数据量大的时候会超时。双指针的解法是从两端开始每次计算当前面积然后移动高度较小的那一端。很多人理解不了为什么移动矮边一定不会漏掉最大值关键在于宽度。两个指针从两端出发宽度是不断减小的。如果移动的是高边宽度在缩小新高度就算更高但面积要取较矮的那条最终高度不可能超过原来的矮边所以面积一定比当前更小。反过来如果移动矮边虽然宽度减小了但新的高度有可能会变大面积才有可能超过当前值。这个贪心策略的正确性是可以用数学归纳严格证明的但实际操作中你只要记住这一个判断移动矮边才有面积变大的可能移动高边完全没有可能。我写这个题的时候会先算面积再移动不要提前移动指针导致面积算错。边界情况就是数组只有两个元素这种情况直接返回唯一的面积即可。3. 链表专题遍历、反转与环检测3.1 链表题的指针基本功链表题让我总结一条最重要的经验修改next之前先把下一个节点保存下来。这句话看似简单实际做题时最容易破功。反转链表里如果你直接执行curr.next prev那原来curr后面的链表就找不到了整条链表直接断掉。链表节点就是一个对象里面装着值和一个指向下一个节点的引用。操作链表本质就是操作引用。很多人搞不清链表头是谁、结尾怎么判断建议画一张图把每个节点画成格子把next画成箭头一步一步跟着代码走一遍比眼睛盯着屏幕看十遍都有用。另一个建议是学会使用哑节点。哑节点就是一个虚拟头节点它本身的val没有任何意义但因为它始终指向链表真正的头节点很多边界情况就不用单独判断了。比如你需要在头部插入节点、删除头节点或者链表可能为空用哑节点可以省掉一堆if-else。3.2 反转链表的两种写法对比反转链表是链表题的老祖宗几乎每次面试都可能遇到。迭代法用一个prev指针记录前驱一个curr指针记录当前节点在循环里先用临时变量保存curr.next再把curr.next指向prev然后整体前移。循环结束后prev恰好是反转后的新头节点。递归法的思路要难理解一些先递归到链表的末尾让最后一个节点成为新链表的头然后在回溯的过程中把每个节点的next反过来指。核心就是head.next.next head和head.next None这两个赋值。很多人在这一步绕晕是因为没想明白递归返回来的值是什么——返回值是已经反转好的链表的头节点而不是当前节点。如果是第一次学递归我建议先画递归栈画出每一层的状态很快就能理顺。我个人的建议是面试优先写迭代法。迭代法空间复杂度O(1)递归法虽然代码短但空间复杂度O(n)而且递归的调用栈深度在链表很长的时候有风险。如果面试官问递归写法你再写出来也不迟。3.3 环形链表 II 的数学推导环形链表I是问有没有环环形链表II要更进一步返回入环的第一个节点。这题用快慢指针先找到相遇点然后有一个经典的数学结论一个指针从链表头出发一个指针从相遇点出发都每次走一步它们最终会在入环点相遇。这个结论很多人会背但要真正理解才有底气。假设链表头到入环点的距离是a入环点到相遇点的距离是b相遇点继续走到入环点的距离是c。慢指针走了ab步快指针走了abcb步。因为快指针速度是慢指针的两倍所以2(ab) abcb化简得到a c。这意味着从链表头到入环点的距离恰好等于从相遇点继续走到入环点的距离。所以两个指针同速走必然同时到达入环点。实现上要注意快指针走两步之前要先判断fast和fast.next都不为空否则会空指针异常。还要记得如果循环结束都没有相遇说明没有环返回None。4. 回溯算法模板、剪枝与去重4.1 回溯本质状态树上的DFS回溯算法本质是一种深度优先搜索它的核心操作就是三个步骤做选择、递归、撤销选择。很多人觉得回溯难是因为没有把它的状态变化想清楚程序在递归中一层层往下走每层都是一个独立的岔路口撤销选择是为了让程序能回到上一层继续探索其他分支。我用一个生活化的例子来解释。你在一个陌生的公园里找出口每个岔路口都试一条路往前走走了一段发现是死路就沿原路退回岔路口再试另一条路。回溯算法里的递归调用就是往前走return就是碰到死路把刚才的选择撤销掉就是回到岔路口。回溯题的状态空间是一个树形结构。树的每一层代表递归的深度树的每一个分支就是一种可能的选择。解题的关键是剪枝——在递归过程中尽早地判断某些分支不可能产生合法解直接跳过。剪枝做得好程序可能从几亿次递归降到几千次这也是为什么很多回溯题都要求先排序。4.2 全排列和组合的差别在哪里全排列和组合都是经典回溯但细节差异非常重要。全排列关注顺序[1,2]和[2,1]是两个不同的排列所以在每一层递归都要遍历所有节点靠一个used数组来标记哪些数字已经被选过避免重复取同一个数字。组合题目不关注顺序[1,2]和[2,1]是同一个组合所以不能让后面的元素再和前面的元素组合一遍否则就会大量重复。处理方式是用一个startIndex参数告诉当前递归从哪个位置开始取数这样就能保证组合中元素的相对顺序是递增的天然去重。如果原数组里还有重复元素那就要再加一层去重逻辑先排序然后在同一层递归里如果当前元素和前一个元素相同并且前一个元素还没被使用过就跳过。这个逻辑很容易写错常见错误是把“前一个元素被使用过”和“前一个元素没被使用过”的条件搞反了。核心思想是保证在同一个树层不重复用相同的值而在同一条树枝上允许连续使用相同值。4.3 组合总和的排序剪枝思路组合总和这个题candidates里的数可以无限次重复使用目标是从中选出一组数使其和等于target。这里有两个处理要点一是递归下一层时的起点传i而不是i1因为当前数字可以重复使用二是排序之后可以提前break因为数组已经升序一旦当前数字比剩余目标值还大后面的数字也一定更大整个循环都可以结束。举一个实际例子candidates为[2,3,6,7]target为7。从2开始2可以用多次路径是2-2-3和为7记录答案然后是2-3还剩2再取3就超过了break然后换分支。如果你不排序在递归里面对大于剩余目标值的数字就不能用break只能continue也是对的但效率差不少。我写回溯的代码时有一个习惯在递归函数开头打印当前状态比如path和remain的值。这个小技巧在调试时特别管用能直观看到搜索的路径和剪枝点。5. 六道题逐一拆解与代码复盘5.1 三数之和先排序再夹逼三数之和的完整代码我习惯这样写def threeSum(nums): nums.sort() n len(nums) res [] for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: left 1 elif total 0: right - 1 else: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res这部分有两个地方容易写错。第一个是外层去重必须写成nums[i] nums[i - 1]不能写成nums[i] nums[i 1]否则会漏掉解。第二个是找到一组解后去重要放在记录答案之后否则可能把本来合法的组合跳过。我上个月用这个题帮朋友做模拟面试她的错误就是去重时机不对用了i1去重结果[ -1, -1, 2 ]这种解直接被漏掉了。所以记住外层i去重总跟前面比找到答案后内层指针再用while跳过重复值。5.2 盛最多水的容器每次移动矮边代码很简单核心逻辑只有几行def maxArea(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans写这个代码的时候我习惯把left和right命名为i和j这样在脑海里更容易对应到公式里的下标。面积计算用的是当前两边高度的较小值乘以宽度。移动哪一边的依据就是比较两边的高度哪个矮就移动哪个。如果高度相等移动哪边都可以任意选一个更简单的方向。这个题的难点不在代码而在证明这样移动不会错过最优解。面试时能画出证明过程会比直接背代码加分不少。我的记忆方法就是一句话“宽度一直在缩小只有提高矮边才有机会得到更大面积。”5.3 反转链表迭代和递归的对比迭代版def reverseList(head): prev None curr head while curr: temp curr.next curr.next prev prev curr curr temp return prev递归版def reverseList(head): if not head or not head.next: return head new_head reverseList(head.next) head.next.next head head.next None return new_head迭代版的核心就是先用temp把后面的链条存住再改当前指针指向prev。我见过好几个同学把这行temp curr.next漏掉导致链表断掉一调试就是空指针特别浪费时间。递归版的理解建议用一层具体例子推假设head是1head.next是22的next是3。reverseList(2)返回以3为头、方向反转后的新链表。这时候2.next还是3所以head.next.next head就是把3的next指向11的next设为None。递归的本质就是把“当前节点后面的链表先反转好”再把当前节点接上去。5.4 环形链表 II快慢指针找入口def detectCycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: slow head while slow ! fast: slow slow.next fast fast.next return slow return None这里的重点在于第一阶段的快慢指针不能跳过相遇。如果链表很长环很大快慢指针会在环内转圈但一定能相遇。第二阶段slow从链表头出发fast从第一次相遇点出发同速向前两者相遇的位置就是入环点。这个题我建议你亲手推一遍数学公式再上机直接背代码容易在面试里被追问推导过程。推导结果就是a c这个等式也是整个算法的灵魂。5.5 全排列used标记当前路径def permute(nums): res [] used [False] * len(nums) path [] def dfs(): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) dfs() path.pop() used[i] False dfs() return res两个关键点第一收集结果时一定要用path[:]拷贝直接append(path)的话后面pop操作会把已经存进去的路径一起改掉。第二递归进入下一层时遍历起点是0而不是startIndex因为排列里顺序不同结果不同每个元素都可能出现在任意位置。5.6 组合总和可重复取数 剪枝def combinationSum(candidates, target): res [] candidates.sort() path [] def dfs(start, remain): if remain 0: res.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] remain: break path.append(candidates[i]) dfs(i, remain - candidates[i]) path.pop() dfs(0, target) return res这个题最关键的代码是dfs(i, remain - candidates[i])传的是i不是i1表示当前数字取完之后还能再取。排序后再加一个if candidates[i] remain: break这就是剪枝。注意是break而不是continue因为排序后后面的数更大全部不合格。有些变体会把条件改成每个数字只能用一次那就把dfs(i, ...)改成dfs(i 1, ...)同时再对同一层重复值做跳过处理。建议你把这两个版本的差距亲手敲一遍感受一下这几行变化的影响力。6. 排坑实录与刷题建议6.1 高频易错点速查表我把今天6道题里容易踩的坑整理成一个表格这些基本都是我自己或身边同学真正犯过的错误| 专题 | 易错场景 | 正确做法 | | 双指针 | 三数之和外层去重写成与后一个比较 | 应与前一个nums[i-1]比较 | | 双指针 | 盛水容器先移动指针再算面积 | 必须先算面积后移动 | | 链表 | 反转链表忘记保存下一个节点 | 用temp curr.next提前保存 | | 链表 | 环形链表的循环条件写成while fast.next | 必须同时判断fast和fast.next不为空 | | 回溯 | 收集结果直接用res.append(path) | 必须用path[:]创建副本 | | 回溯 | 组合总和递归下一层传i1 | 可重复取数时传i不可重复传i1 |这个表格建议你保存下来每次做同类题之前看一眼能省很多调试时间。6.2 实际调试中的体会与习惯我今天做这6道题每道都刻意跑了一遍极端用例。三数之和我试了全0数组结果应该是[[0,0,0]]这个用例能验证去重逻辑是否正确。盛水容器我用高度单调递增的数组验证每一步移动都没有漏掉最大值。反转链表我专门试了只有一个节点的链表确保返回的prev确实是原节点而不是None。环形链表II我构造了一个头节点就在环里的链表这种情况第二阶段循环一次都不执行直接返回的就是头节点。调试链表题最有效的方法还是画图。我用白板把反转链表的前两步画出来每个节点一个方框next是箭头然后拿手指头跟着代码走一遍比在内存里反复打印next值直观得多。回溯题调试我用的是打印递归参数的方法这就像给迷宫探险者一路留下走过的痕迹回头排查时非常清楚。最后分享一个我做回溯题的小习惯。每写一个回溯函数我都先定义好它的参数语义再动笔。比如全排列里的dfs()不传任何参数因为路径信息都在path和used里组合总和里的dfs(start, remain)负责告诉递归“你现在可以从哪个位置开始、目标还剩多少”。参数越少越不容易混乱但该有状态的也不要省。很多复杂度高的回溯题错误都发生在参数语义不清上。这个经验在你后面做子集、N皇后这类题时会非常受用。