双指针这套笔记的第二篇隔了快两周才动笔主要是想把同一套思路在不同数据结构上的应用一次性理清楚。双指针的核心其实特别朴素在数组、链表或者字符串上用两个坐标或者两个链表节点引用按照某种规律同时移动替代嵌套循环里的反复扫描从而把时间复杂度从O(n²)压到O(n)。这篇笔记覆盖相向双指针、同向双指针、快慢指针和滑动窗口四个形态每部分都给Python模板代码、边界分析和个人踩坑记录适合正在刷算法题、准备面试或者被双指针题目绕晕的朋友慢慢读。1. 双指针到底在解决什么问题1.1 暴力解法为什么慢O(n²)的瓶颈在哪很多双指针题目第一反应都是暴力。拿有序数组的两数之和来说最直觉的写法就是两层循环外层定一个数内层找另一个两层循环意味着每个数都要跟后面所有数比较一轮。数组长度是n比较次数大约是n(n-1)/2也就是O(n²)。n小的时候无所谓一旦n到十万级别计算量就到百亿次显然扛不住。暴力解法慢的根本原因在于它在做大量无效比较。比如有序数组里left小、right大的场景当nums[left] nums[right]已经大于target时对当前left来说所有比right更大的索引对应的值只会更大相加结果只会更大根本不可能等于target。暴力循环意识不到这种单调性还傻乎乎地把所有组合都试一遍。双指针之所以快就是因为它利用数据本身的单调性或者题目约束把不可能存在解的区域直接剪掉。每一步至少有一个指针朝正确方向移动两个指针总共移动n次扫描一遍就结束算法复杂度自然掉到O(n)。核心不是“用两个变量”这个形式而是“每次移动都能排除一批无效候选”这个思想。1.2 双指针的两大基础模型相向与同向刚接触双指针的人容易把题目里出现两个索引都叫双指针但不同题目里指针的移动方向完全不一样解题逻辑也不同。我习惯把双指针分成两大类。第一类是相向双指针也叫左右指针、对撞指针。left从数组头部出发right从尾部出发while left right循环根据条件决定移动left还是移动right最终两个指针在中间某个位置相遇。这类题型一般要求数据有序或者需要把数组两端的信息同时纳入考量典型题目包括有序数组两数之和、三数之和、回文串判定、盛最多水的容器。第二类是同向双指针left和right从同一个端点出发right先走left在后面追形成“快慢”或“覆盖写”的效果。这里面又分两种链表场景叫快慢指针用来找环、找中点数组场景里常见的是快慢索引加滑动窗口。同向双指针的价值在于它维护的是一个“区间”的状态而不只是两个孤立点的状态。这两类模型虽然都叫双指针但写代码时的循环条件和指针更新策略很不一样相向的核心是“判断结果然后决定丢弃左边还是右边”同向的核心是“什么时候扩展右边界什么时候收缩左边界”。搞清楚这一点后面做题就能少走很多弯路。1.3 快速判断一道题能不能用双指针我整理了一套自己的判断流程不一定严谨但实战中挺管用。第一题目给的数据结构是不是数组、链表或者字符串这三类数据结构天然存在“位置”的概念指针才有地方落。第二数据是不是有序或者题解是否依赖排序。相向双指针几乎都建立在有序数组之上无序的话先排序再说。第三问题是否可以用“维护一个区间”或者“比较两个端点”的方式来描述比如求子数组最长长度、找满足条件的两个元素、判断是否存在环这类问题双指针有天然优势。另一个不太被人提到的信号是当暴力解法是双层循环、且内层循环的指针在外层循环中只进不退时大概率可以改成双指针。说白了只要内层指针不会回头就说明整个扫描过程是线性的完全可以用“一快一慢”两个指针在同一趟遍历里把事情干完。反过来如果内层指针需要反复回退比如无序数组里找任意两个数的组合那更合适的是哈希表而不是双指针。能判断“什么时候不该用双指针”其实比知道“什么时候该用”更重要面试里很多人栽在这上面。2. 相向双指针有序数组的黄金搭档2.1 有序数组两数之和最经典入门题这道题可以说是相向双指针的“hello world”。题目很直接给定一个升序排序的整数数组nums和一个目标值target请你在数组中找出和为target的两个整数返回它们的下标。暴力就不说了直接看双指针思路。left指向数组第一个元素right指向最后一个元素计算sum nums[left] nums[right]。如果sum等于target直接返回结果。如果sum小于target说明整体和偏小需要把和变大而数组是有序的只能把left往右移让nums[left]变大。如果sum大于target说明整体和偏大把right往左移让nums[right]变小。不断重复直到left和right相遇。def two_sum_sorted(nums: list[int], target: int) - list[int]: left, right 0, len(nums) - 1 while left right: current nums[left] nums[right] if current target: return [left, right] if current target: left 1 else: right - 1 return []这段代码我建议背下来当模板因为后续三数之和、四数之和的内层循环几乎都是它的变体。值得留意的细节有两个。第一循环条件是left right而不是left right因为当left等于right时两个指针指向同一个元素不满足“两个整数”的约束再继续循环要么重复计算要么越界。第二每次指针移动后不需要回头因为当前组合已经被判定为不可能回头只会重复已经排除的计算。2.2 三数之和固定一个再双指针注意去重两数之和理解后三数之和就是一个“固定一个元素剩下两个变成两数之和”的思路。先把数组排序然后外层循环固定nums[i]内层用相向双指针在i1到数组末尾之间找两个数使得三数之和等于target。这题最大的坑不在双指针本身而在去重。排序之后相邻的相同元素会被排在一起。如果不去重同一个三元组会被枚举很多次最终结果里出现大量重复。标准做法是两层去重外层循环里如果i大于0且nums[i]等于nums[i - 1]直接continue跳过内层双指针找到一组答案后left和right都要跳过所有重复值再各自移动一步。def three_sum(nums: list[int], target: int) - list[list[int]]: nums.sort() result [] n len(nums) for i in range(n - 2): 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 target: result.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 elif total target: left 1 else: right - 1 return result这里外层循环的范围是range(n - 2)因为至少还要留两个位置给left和right这个细节很多人第一次写会写成n然后在内层出现left越界。去重的时机也很关键如果只在输出结果后用set去重代码虽然简单但时间复杂度会退化因为重复的扫描并没有省掉。跳过重复值的本质是“在枚举层面剪枝”而不是“在输出层面过滤”。2.3 再看两道变体回文串判定与盛最多水的容器回文串判定是最简单的相向双指针题。一个字符串是回文串当且仅当首尾字符相等、去掉首尾后剩下的子串仍然是回文串。用left和right从两端往中间走发现不等直接返回False全程扫描完返回True。这题虽然简单但它是后续很多字符串题目的基础比如“验证回文串”要求在比较时跳过非字母数字字符就需要在while循环里加两个内层while过滤本质上还是同一套骨架。def is_palindrome(s: str) - bool: left, right 0, len(s) - 1 while left right: if s[left] ! s[right]: return False left 1 right - 1 return True盛最多水的容器是另一道经典题题目给一个高度数组height每个元素表示一个竖直挡板的高度要求选两个挡板让它们构成的容器能装最多水。容器的盛水量等于两个挡板之间的距离乘以两个挡板中较矮那个的高度。最直接的想法是枚举所有挡板对但那是O(n²)。双指针的思路是left和right初始在数组两端计算当前容量然后每次把较矮的那一侧指针往中间移动。为什么移动较矮的那一侧因为容器高度取决于矮板如果移高板宽度变小、高度最多不变容量只可能变小如果移矮板虽然宽度变小但高度可能变大容量才有变大的可能。这个“贪心”的依据其实也是单调性分析较矮的一侧不移动的话它跟任何中间位置组合都不可能超过当前最优解可以放心剪枝。这道题也和很多“最优区间”问题一样双指针的正确性来自于“每次排除掉一侧不会错过全局最优解”的论证。3. 同向双指针与快慢指针链表和数组的隐藏利器3.1 链表环检测与链表中点相向双指针主要服务于数组和字符串链表场景下更常用的是同向双指针也就是快慢指针。最著名的应用是环检测给定一个链表判断它是否带环。想象两个人在环形跑道上跑步速度快的那个人迟早会追上速度慢的那个人这就是Floyd判圈算法的核心直觉。def has_cycle(head) - bool: slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False这里的while条件写成fast and fast.next是为了保证fast能连续走两步而不触发空指针。如果链表没有环fast会先走到链表尾部循环正常退出返回False。如果链表有环fast和slow最终会在环内相遇。这个算法的时间复杂度是O(n)空间复杂度是O(1)比用哈希表记录访问过的节点省空间得多。快慢指针另一个常见应用是找链表中点。slow每次走一步fast每次走两步fast到达链表末尾时slow正好停在中间位置。对奇数长度链表slow是正中间那个节点对偶数长度slow是前半段的最后一个节点这个细节在“回文链表”这类题里会影响代码逻辑用的时候要心里有数。这类“一个走一步、一个走两步”的模式本质上是用速度差让快指针成为慢指针的“探路者”慢指针走到的位置可以被精确控制。3.2 数组原地去重覆盖写思想同向双指针在数组里最经典的应用是原地去重。题目要求给一个有序数组原地去重让每个元素最多出现一次返回新的长度。所谓原地就是不能新建数组只能通过覆盖数组元素来完成。这时候用两个索引一个慢索引write标记当前写入位置一个快索引read扫描整个数组。read每遇到一个不重复的元素就把它写到write位置然后write加一。def remove_duplicates(nums: list[int]) - int: if not nums: return 0 write 0 for read in range(1, len(nums)): if nums[read] ! nums[write]: write 1 nums[write] nums[read] return write 1这个写法的核心思想是“快指针负责发现新元素慢指针负责记录覆盖点”。为什么结果是write 1因为write是最后一个有效元素的下标有效的元素个数等于最后一个下标加一。很多人在这一步容易搞混建议记一个简单规则返回的是“有效区域的长度”不是最后一个元素的下标。这里还有个小优化点很多题目不只是要求每个元素出现一次还要求最多出现两次比如“有序数组中的重复项II”。思路几乎一样只是比较目标从write改成write - 1也就是允许当前元素跟上上个写入的元素相同。这类变体很多但核心都是覆盖写理解了慢指针的含义就能举一反三。还有一个容易被忽略的点原地去重之后数组后半段会残留旧值但题目只关心新长度所以不用清理别画蛇添足去删元素那会把O(n)复杂度变成O(n²)。3.3 滑动窗口同向双指针的进阶形态滑动窗口本质上也是两个同向指针但它的重点不是“比较两个指针指向的元素”而是“维护left到right之间的这个子区间使它满足某种条件”。我把它算作双指针的进阶形态因为模板更加程式化。最典型的入门题是“无重复字符的最长子串”给定一个字符串找出不含重复字符的最长连续子串的长度。def length_of_longest_substring(s: str) - int: char_set set() left 0 max_len 0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left 1 char_set.add(s[right]) max_len max(max_len, right - left 1) return max_len这道题外层for循环控制right扩展右边界内层while在发现重复字符时不断收缩left直到窗口恢复“无重复”状态。每个字符最多被left移除一次、被right加入一次整体仍然是O(n)。理解滑动窗口的关键是回答一个问题什么时候收缩left答案是窗口条件被破坏的时候。具体到这道题就是新字符已经在窗口里了必须把左侧重复字符及其之前的所有字符全部排出去。滑动窗口延续到后面还有定长窗口、最长/最短可行窗口等变形但核心都是“右边界扩张、左边界收缩”这两个动作。很多人在刚接触时不适应内层while总觉得它会把复杂度变成O(n²)实际上每个元素进出窗口各一次均摊下来就是O(n)不要被内层循环吓到。写滑动窗口时还有个经验窗口状态不一定要用set很多题目用counter字典或者普通变量就够了状态维护得越轻量代码越不容易出错。4. Python代码实现的细节与性能分析4.1 循环边界与指针更新的代码风格双指针的Python实现坑点非常集中我总结下来主要是循环边界、指针更新顺序和返回值三个地方。先说循环边界相向双指针用while left right快慢指针里链表场景用while fast and fast.next数组场景常用for循环驱动右指针内层再套一个while处理左指针。写之前先想清楚“指针会不会越界”“两个指针能不能指向同一个位置”想清楚再动手。指针更新顺序是另一个容易出错的地方。相向双指针里如果当前和小于target应该先判断再移动顺序不能反。有些新手喜欢在循环开头统一更新指针结果发现答案丢失或者死循环。指针更新必须紧跟着判断分支走每个分支只做一件事要么返回要么移动left要么移动right。关于代码风格我给个建议变量名直接用left、right、slow、fast不要用i、j、k混着来。双指针题目的核心就是搞清楚每个变量的职责写清楚命名能避免一半的混乱。另外Python不需要担心整数溢出但需要担心索引越界尤其是while fast and fast.next这种条件一旦写成while fast.next and fast链表只有一个节点时直接报错这个顺序问题很多人第一遍都会踩。4.2 时间复杂度与空间复杂度全梳理双指针题目的复杂度分析其实非常统一绝大多数双指针解法每个指针在整个算法过程中只会朝着一个方向移动总移动次数不超过n所以时间复杂度是O(n)。如果题目需要先排序那总复杂度是O(n log n)加O(n)比如三数之和基于比较的排序跑不掉。如果外层还有一层固定循环像三数之和那样整体就是O(n²)但这已经比暴力的O(n³)好很多了。空间复杂度方面双指针本身只用了常数个变量空间复杂度是O(1)这是它对比哈希表方案的一大优势。比如链表环检测用哈希表记录节点是O(n)空间快慢指针只需要O(1)。但要注意滑动窗口如果用了set或者dict来维护窗口内容那空间复杂度是O(k)k是窗口大小最坏情况下等于n。我整理了一个常见题型的复杂度表方便复习时对照着看。题目双指针方案时间复杂度空间复杂度指针类型有序数组两数之和O(n)O(1)相向三数之和O(n²)含排序O(n log n)O(1)结果数组除外外层固定相向回文串判定O(n)O(1)相向盛最多水的容器O(n)O(1)相向贪心链表环检测O(n)O(1)快慢数组原地去重O(n)O(1)同向覆盖无重复字符最长子串O(n)O(k)滑动窗口这张表里最容易被问倒的是“为什么O(n)是均摊来的”尤其滑动窗口。停留在窗口里的每个元素最多进出一次所以总操作数是O(n)这就是均摊分析的直观理解。面试里被追问复杂度的原理时能用“每个指针最多移动n次”来解释基本就能说服面试官了。4.3 边界陷阱与调试方法论双指针代码的边界条件可以用一串边界测试用例来检验空数组、只有一个元素的数组、全部元素相同的数组、数组两端恰好是答案的情况、target极小或极大的情况。我在本地刷题时习惯先把这些用例跑一遍再提交能省下不少提交失败的次数。调试双指针题目最有效的工具其实是打印。在while循环里加一行print把left、right、当前和或者当前窗口状态打出来很快就能定位问题。特别是死循环打印后你会发现指针根本没在动或者动了几次又开始回退。# 调试示例打印两数之和的指针状态 def two_sum_debug(nums, target): left, right 0, len(nums) - 1 while left right: current nums[left] nums[right] print(fleft{left}, right{right}, current{current}) # 关键调试行 if current target: return [left, right] if current target: left 1 else: right - 1 return []另一个实用技巧是给代码加assert。比如在指针更新后断言left right、断言索引没有越界虽然提交前要删掉但开发阶段能帮你快速暴露逻辑错误。这类代码在面试中也很加分能说明你有意识地处理边界条件。我自己的习惯是先加调试行跑通小用例再删掉调试行直接提交这样既高效又不会把调试代码带到线上。5. 常见问题与排查技巧实录5.1 死循环、越界、漏解三大高频bug双指针题目刷多了会发现错误基本集中在三类。第一类是死循环。最常见的原因是循环条件写错比如while left right但循环体内两个分支都没有移动指针或者指针移动的逻辑被一个错误的if包住了。另一个原因是移动步长写成了0比如left 0这种低级错误或者本来想left 1结果写成left 1直接把指针重置到开头无限循环。第二类是索引越界。数组场景里要么是right初始值用了len(nums)而不是len(nums) - 1要么是在循环体内访问了nums[right 1]这种越界下标。链表场景里写fast.next.next时没有先判断fast.next是否为空导致空指针。这些都是“先访问后判断”的典型写法改成“先判断后访问”就能解决。第三类是漏解。相向双指针里如果判断条件用错了方向比如和小于target时把right左移会导致所有需要right保持住的解全部丢失。三数之和里如果去重逻辑写错或者没写要么结果重复要么把本应存在的解跳过了。漏解比死循环还难查因为没有报错只能靠对拍或者跟暴力解法对比才能发现。我在本地做题的时候会额外写一个暴力版本专门用来跟双指针版本对拍这是查漏解最稳的办法。5.2 一段真实踩坑记录的复盘我想分享一个真实踩过的坑。有一次写三数之和外层循环我用的是range(n)而不是range(n - 2)然后在内层初始化的地方写了left, right i 1, n - 1。乍看好像没问题当i跑到n - 1时left n直接越界。更麻烦的是当i跑到n - 2时left n - 1left等于right内层while left right直接不执行代码不报错但答案少了一大截。当时我排查了很久最后是在一个退出的用例上打印了left和right才反应过来内外层循环的边界没有联动。外层循环负责固定第一个数它必须保证后面至少有两个位置给left和right所以上限必须是n - 2。这个错误让我养成一个习惯每次写完双指针先手动模拟数据量最小的用例比如三个元素、四个元素各跑一遍把指针行为手动走查一次很多边界问题在走查阶段就暴露了。这类问题其实都能通过“最小用例走查”提前发现。三数之和的最小用例就是三个元素手动走一遍就能看到i的上界和left、right的关系。如果都用调试器或者提交后再看报错效率低还容易打击信心。手动走查看起来笨但它是建立“指针运动直觉”最快的路径尤其是对相向双指针的收敛过程。5.3 双指针题目的通用自查清单在多次提交失败之后我整理了一张自查清单现在每次写完双指针代码都会对着过一遍。先检查循环条件数组相向双指针用left right链表快慢用fast and fast.next滑动窗口的right用for驱动left用while收缩。再检查指针初始化相向的right是len(nums) - 1不是len(nums)链表的slow和fast都指向head。接着检查指针更新每个分支都要有且仅有一个指针更新确认没有遗漏分支、没有更新错方向。然后检查重复跳过三数之和这类题外层和内层都必须在合适的位置跳过重复值顺序不能颠倒。最后检查返回值返回的是下标还是值、是新长度还是长度减一跟题目要求一一对照。这张清单看起来很简单但每一条都来自实际踩坑。我刚学双指针那会儿几乎每道题都要错一遍后来固定这套流程通过率肉眼可见地上涨。写代码之前花三十秒把清单在脑子里过一遍比写完再调试省时间得多。还有一个心态上的建议双指针题目出错很正常它不是那种“一次就能写对”的题型别因为两次提交失败就怀疑自己把错误记录到笔记里下次就能避开。6. 从双指针出发的后续学习路线6.1 双指针到滑动窗口的进阶路径双指针这一块学到后面会明显感觉题目在朝两个方向延伸一个方向是更复杂的窗口维护比如定长滑动窗口、需要维护最大值或最小值的窗口这类题目会引入单调队列或者堆已经不是单纯的双指针了另一个方向是双指针和其他算法的组合比如排序加双指针、二分搜索加双指针、哈希表加双指针组合题的思考量会明显上一个台阶。我的建议是先把这篇笔记里的七道核心题吃透再进入滑动窗口专题。判断标准很简单看到题目能在一分钟之内说出用相向还是同向、循环条件怎么写、指针什么时候动就算过关。如果还需要想很久说明还没到进阶阶段不要急着刷难题基础题多刷几遍效果更好。进阶阶段推荐从“长度最小的子数组”“水果成篮”“最大连续1的个数III”这类滑动窗口题开始它们的共同点是套同一个模板right扩展条件破坏时left收缩窗口状态用变量维护。等这十几道题做完双指针的框架感就真正建立了之后遇到“三指针”“多指针”的组合题也不会觉得陌生因为它们本质上是双指针思路的延伸。6.2 我的练习方法与题单建议最后分享一点个人经验。我刷双指针题目时不追求题量追求“同一道题用多种方法解”。比如看到两数之和我会先写暴力再写双指针再想如果用哈希表怎么解然后对比三种方案的适用条件。这个习惯让我对方法的边界理解得更清楚哈希表适合无序数组双指针适合有序数组或者允许排序的场景。理解到这一层考试、面试时才能快速选对方法。题单方面我按顺序推荐这些题有序数组的两数之和、三数之和、四数之和、验证回文串、盛最多水的容器、链表环检测、链表中点、原地去重、无重复字符的最长子串、长度最小的子数组、水果成篮、最大连续1的个数III。每道题做完都做一下总结写清楚指针在什么条件下移动、为什么这个条件下移动是对的、如果换个条件会出什么问题。我把这些总结都存在笔记里复习的时候翻一遍比重新刷一遍题效率高得多。学习双指针这件事到后期拼的其实不是记忆力而是对“指针为什么这么移动”的理解深度。我在实际刷题中最大的体会是双指针的模板很好背难的是判断什么时候套哪个模板、边界条件怎么处理这些只能靠反复的题目训练和复盘来积累。碰到一道题想不出双指针解法也别急先看暴力思路再分析暴力里哪些比较是无效的当你亲手把那些无效比较剪掉的时候双指针的思路自然会浮现出来。