双指针在Python算法题里的地位有点像炒菜时的“热锅凉油”——看似基础却决定了后面很多技巧能不能顺利展开。很多初学者学完Python基础语法后刷LeetCode第一题就开始卡壳原因往往不是不会写代码而是不知道用什么样的“遍历结构”去解决问题。双指针恰好就是那个最快见效的突破口它把很多原本需要两重循环才能搞定的问题直接砍成了一次遍历时间复杂度从O(n^2)降到O(n)空间复杂度还能保持在O(1)。这篇文章我打算用完整的Python代码示例把双指针的两种基本形态、典型应用场景、边界条件处理和排查经验一次性讲透适合正在准备算法面试的人也适合学完Python基础想做算法进阶的读者。我自己在带新人刷题时发现一个规律绝大多数人不是看不懂双指针的解法而是不知道“什么时候该用双指针”“指针该怎么移动”。这篇文章就围绕这两个核心问题展开。1. 双指针技巧的核心设计思路1.1 双指针是什么两种基本形态先给一个准确但不绕的定义双指针就是在遍历数组、字符串或链表这类线性结构时不是用一个下标或者一个节点去从头扫到尾而是用两个下标也就是两个“指针”协同配合共同完成搜索、覆盖或比较的工作。这两个指针的关系只有两种相向双指针一个指针从最左边出发一个指针从最右边出发逐步向中间靠拢。典型场景就是有序数组的二分查找变体、回文串判断、原地反转数组。同向双指针两个指针都从同一端出发但移动速度不一样。典型场景是快慢指针检测链表环、滑动窗口求最长连续子串、原地删除数组重复元素。很多资料会把滑动窗口单列出来讲但本质上滑动窗口就是同向双指针的一种变体只不过更强调“窗口”这个抽象概念。你先记住这个框架后面写代码时思路会清晰很多。这个技巧的精髓在于两个指针并不需要真正地去“指”内存地址在Python里它们通常就是整数下标。理解成两个人站在数组的不同位置各自按规则往某个方向走就对了。1.2 为什么双指针能省时间单调性带来的剪枝要想真正掌握双指针光会套模板不够必须理解它为什么能省时间否则遇到变形题还是懵。拿最经典的两数之和来说。给定一个有序数组numbers和一个目标值target要找两个数使它们的和等于target。暴力做法是两层for循环把每一对组合都试一遍时间复杂度O(n^2)。假如数组长度是10万暴力循环就需要跑约50亿次基本没法用。那为什么双指针能做到O(n)呢关键在于输入的数组是有序的这给了我们一个非常重要的性质——单调性。数组最左边是当前范围内最小的数最右边是当前范围内最大的数。设left 0right len(numbers) - 1那么current_sum numbers[left] numbers[right]就是当前范围内能取到的“最大和的最小情况”。比较current_sum和target如果current_sum等于target正好找到答案直接返回。如果current_sum小于target说明两个数总和太小了。因为numbers[right]已经是当前最大只有把left往右移动让较小的那个数变大一点总和才可能增大。此时left左侧的所有数和numbers[right]的组合都不可能等于target被一次性排除。如果current_sum大于target说明两个数总和太大了。因为numbers[left]已经是当前最小只有把right往左移动让较大的那个数变小一点总和才可能减小。此时right右侧的所有数和numbers[left]的组合也全部被排除。每次移动一个指针都会排除一整批不可能的组合。整个过程最多移动n步所以是O(n)。这就是双指针高效的核心秘密——利用单调性在一次遍历中剪掉大量无效枚举。1.3 适用场景快照什么时候优先想双指针从实际刷题经验来看下面这几类特征是双指针的“高发区”数据是数组、字符串、链表这类线性结构而且要求原地处理或者比较。题目里提到“有序”“连续”“子数组”“子串”这些关键词。暴力解法能写出来但时间复杂度明显太高需要优化掉一层循环。题目要求空间复杂度尽量低最好不要用字典、集合等额外数据结构。反过来如果数据是无序的且不排序也OK那么用哈希表往往更合适如果数据是树形结构双指针就不太适用该用递归或BFS/DFS还是得用。我一般建议初学者先把双指针和哈希表这两种思路放在一起对比学习因为它们正好覆盖了大多数数组类题目的优化方向。2. 基础形态一相向双指针专门解决有序数组问题2.1 两数之和II从暴力循环到双指针优化先看最经典的入口题。力扣上的“两数之和 II - 输入有序数组”就是一个完美的教学案例。题目要求返回两个数的下标并且下标从1开始计数。为了演示方便我按下标从0开始写你自己在做题时改一下返回值的偏移即可。def two_sum(numbers, target): left, right 0, len(numbers) - 1 while left right: current_sum numbers[left] numbers[right] if current_sum target: return [left, right] elif current_sum target: left 1 else: right - 1 return []这段代码的核心逻辑已经在1.2节解释了。这里补充几个容易出错的细节第一循环条件必须是left right而不是left right。因为题目要求找两个不同的数如果允许left right那等于同一个数自己加自己在大多数题目里是违规的而且可能返回错误答案。即使题目允许同一个元素用两次那也应该单独处理不影响这个模板。第二为什么current_sum target时移动left而不是right因为数组有序numbers[left]已经是当前区间内最小的数如果把它和最大的numbers[right]加起来都小于target那么把right往左移只会让总和更小完全没必要。这一步是整个算法“剪枝”的关键也是面试官最喜欢问的问题。第三最后return []不要漏。虽然题目保证有解但作为一个健壮的函数还是要把无解分支写清楚。2.2 回文串判断与原地反转数组相向双指针的第二个高频应用是判断回文串。回文就是正着读和倒着读一样比如racecar、上海自来水来自海上。判断的方法就是两个指针从两端往中间走一旦发现对应位置字符不相等立即返回False。def is_palindrome(s): left, right 0, len(s) - 1 while left right: if s[left] ! s[right]: return False left 1 right - 1 return True这个写法很简洁但要注意一个隐藏问题如果字符串里有空格、标点且题目要求忽略这些非字母数字字符那就需要在比较前做预处理。我一般是这样处理的def is_palindrome_alpha(s): cleaned .join(ch.lower() for ch in s if ch.isalnum()) left, right 0, len(cleaned) - 1 while left right: if cleaned[left] ! cleaned[right]: return False left 1 right - 1 return True不过预处理会额外占用O(n)空间。如果面试官要求严格的空间限制可以用while left right在循环内部跳过非字母数字字符但那样代码会复杂一点。实际工作中我倾向于先写清楚、可读性高的版本再根据需求优化。原地反转数组也是同一个套路。Python里虽然有nums.reverse()但理解底层过程仍然重要因为反转思想会迁移到很多变形题里比如字符串单词反转、旋转数组。def reverse_list(nums): left, right 0, len(nums) - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 return nums这里特别提醒Python新手nums[left], nums[right] nums[right], nums[left]这个写法在Python里是安全的它等价于用一个临时变量完成交换。在C语言或Java里你可能会写temp nums[left]; nums[left] nums[right]; nums[right] temp;但在Python里直接用多元赋值就行简洁且不易出错。2.3 相向双指针的边界哲学做相向双指针最容易翻车的地方就是循环结束的条件到底该用还是以及最后left和right相遇时指向的元素到底要不要处理。我的经验是这样的先问自己当left right时这个正中间的元素还需要比较吗判断回文串时中间元素和它自己比较没有意义所以while left right结束时不处理中间元素。反转数组时中间元素不用交换所以同样是while left right。二分查找时如果搜索区间是闭区间[left, right]那么left right时还剩下最后一个候选元素必须再判断一次所以用while left right。说白了边界条件的核心不是死记硬背而是搞清楚循环不变量每次循环开始时未被检查或未处理的数据范围是什么。只要把不变量想清楚边界就不会错。还有一个实用小技巧写完代码后用长度分别为0、1、2、3的极简输入各跑一遍。比如空数组、[1]、[1,2]、[1,2,3]人工推演一下循环过程绝大多数边界问题当场就能暴露。3. 基础形态二同向双指针覆盖快慢指针与滑动窗口3.1 快慢指针链表环检测与找中点同向双指针最典型的应用是判断链表是否有环。Floyd判圈算法大家应该都听过一个快指针每次走两步一个慢指针每次走一步如果链表里有环快指针迟早会追上慢指针并相遇如果没有环快指针会先走到链表末尾。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False这里有个细节值得展开为什么快指针每次走两步而不是走三步、四步因为慢指针每次走一步如果环的长度是L那么快指针相对慢指针的速度差是每轮一步。这意味着每经过一轮快指针离慢指针的距离就会缩短1所以最多走L轮两者必然相遇。如果速度差不是1比如快指针每次走三步那快指针相对慢指针速度差是2当环的长度为偶数时两个指针可能在环里一直交替错过虽然实际上通过数学可以证明在某些条件下也会相遇但分析起来麻烦很多。所以在判圈问题上快指针走两步、慢指针走一步是最稳妥、最容易证明的方案。顺带说一下找链表中点同样用一快一慢两个指针快指针到末尾时慢指针正好在中点位置。这个技巧在“回文链表”这类题目里很常用因为你可以先找到中点再把后半段反转然后用相向双指针比较。3.2 快慢指针做原地数组压缩同向双指针不只用在链表上数组里同样常见典型题目是“移除元素”。题目要求原地删除所有值等于val的元素返回新数组的长度。暴力做法是每删除一个元素就把后续所有元素往前移时间复杂度O(n^2)。用快慢指针可以做到一趟遍历完成def remove_element(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow这里的两个指针分别扮演什么角色fast负责从头到尾扫描原数组它像侦察兵逐个检查每个元素是否该保留。slow负责维护“有效区域”的末尾位置它像施工队把该保留的元素搬到前面的空位。每次遇到一个不等于val的元素就把它写到nums[slow]然后slow前进一格。扫描结束后nums的前slow个位置就是删除后的有效内容后面的旧数据不用管因为题目只要求前slow长度有效。这个模式的通用性很强稍微改一下判断条件就能解决“删除有序数组中的重复项”“把数组中的所有0移动到末尾”等问题。比如删除重复项的版本def remove_duplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1注意这个版本是“先移动slow再写入”因为得先给新元素腾位置。和移除元素那版的区别在于slow初始值是0还是1写入前slow是否先加1。这两个细节很容易搞混我建议你把两个函数并排放在一起对比着看自己推演一遍nums [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]这个过程。3.3 滑动窗口最长无重复子串的完整实现滑动窗口是双指针里最“实战”的内容也是面试中出现频率最高的类型之一。我直接拿“最长无重复字符的子串”这个经典题来讲。题目是这样的给定一个字符串找出其中不含有重复字符的最长连续子串的长度。比如abcabcbb答案是abc长度3。暴力思路是枚举所有起点再对每个起点不断扩展终点直到出现重复字符。每个起点都要重新扫描复杂度O(n^2)。滑动窗口版本可以用O(n)解决def length_of_longest_substring(s): last_seen {} left 0 max_len 0 for right, ch in enumerate(s): if ch in last_seen and last_seen[ch] left: left last_seen[ch] 1 last_seen[ch] right max_len max(max_len, right - left 1) return max_len我来解释这段代码为什么这么写。窗口用[left, right]表示right每轮向右扩展一个字符。last_seen字典记录每个字符最近一次出现的位置。关键分支是那句if ch in last_seen and last_seen[ch] left如果当前字符之前在窗口内出现过即last_seen[ch] left说明窗口已经“不合法”了需要把left跳到该字符上次出现位置的下一个位置把重复字符排挤出去。如果当前字符之前出现过但位置在left左边说明那个旧位置已经被移出窗口了当前字符在新窗口里没有冲突不用动left。为什么要判断last_seen[ch] left因为如果不判断遇到s abba这种情况就会出错。我们跑一下right0字符aleft0记录last_seen{a: 0}max_len1。right1字符bleft0记录last_seen{a: 0, b: 1}max_len2。right2字符blast_seen[b]1 left0所以left 1 1 2更新last_seen[b]2窗口长度2-211max_len保持2。right3字符alast_seen[a]0但注意last_seen[a]0不再大于等于left2说明这个a在旧位置已经被甩出了当前窗口当前窗口里并没有a所以left不动。窗口长度3-212max_len保持2。如果去掉last_seen[ch] left这个判断第4步就会把left误设为last_seen[a] 1 1导致窗口变成[1, 3]错误地认为找到了长度3的无重复子串bba。这个坑几乎每个初学者都会踩一次。4. 实战中的常见问题与排查技巧4.1 边界条件速查表写双指针题边界条件往往是运行时错误的重灾区。我把常见场景整理成一张速查表你写之前扫一眼能少走很多弯路。输入情况典型处理方式常出问题的点空数组或空字符串函数开头直接返回空结果或0nums[0]索引越界长度为1的数组根据题意判断是否需要特殊处理循环条件写错导致直接进不了循环所有元素都相同快慢指针能否正确推进slow的初始值写错返回值差1目标值不存在循环结束后要有默认返回值忘记return []或return -1负数参与比较有序性依然成立双指针照常用拿绝对值大小做判断逻辑混淆链表为空或只有一个节点判环和找中点都要提前处理fast.next.next触发空指针异常比如回文判断空字符串按定义是回文很多人的代码在s 时会直接索引越界正确的做法是先判断if len(s) 1: return True。这种“防御性写法”在算法面试里很加分因为面试官能看到你考虑问题是否周全。4.2 死循环与越界的几个经典现场我在自己调试和帮人review代码时遇到最多的问题就是死循环和越界。这里分享几个真实翻车现场。第一个死循环案例某个同学写两数之和时循环体里只写了判断和更新却没有在current_sum target时返回结果永远卡在那个分支里。这种问题倒好办跑一遍测试用例看哪个样例无法结束加一行print(left, right)立刻就能定位。第二个越界案例链表判环时很多人会写成while fast.next and fast.next.next但忽略了一开始的while fast and fast.next。当fast本身已经是None时再访问fast.next会直接抛AttributeError。正确做法是先把fast本身是否为None判断掉。第三个逻辑疏忽案例相向双指针的循环里先移动指针还是先比较值顺序不能乱。比如反转数组必须在交换后再同时移动两个指针。如果你在某一轮只移动了一个指针下一次循环条件就可能产生错位导致交换错元素。我调试时最常用的方法是在关键循环里临时加print(left, right, nums[left], nums[right])手动运行两三轮对照手推结果。很多看似玄学的bug用这个方法五分钟就能定位。在LeetCode上跑不通的时候别急着怀疑编译器先把样例缩到最小自己走一遍。4.3 在本地快速验证双指针代码的小建议很多刚配好Python环境的朋友喜欢把代码直接贴到在线评测系统里跑失败了再一遍遍提交这样效率其实很低。我建议你在本地写几个断言把核心测试用例一次性跑完。比如刚才的最长无重复子串可以这样写assert length_of_longest_substring(abcabcbb) 3 assert length_of_longest_substring(bbbbb) 1 assert length_of_longest_substring(pwwkew) 3 assert length_of_longest_substring() 0 assert length_of_longest_substring(au) 2 print(all tests passed)用assert的好处是一旦某个用例不通过程序会立即终止并标明是哪一行。我要强调一下本地写测试断言不是浪费时间恰恰是最快的学习方式。它能帮你在短时间内跑大量输入把边界条件和循环不变量彻底吃透。至于环境本身Python 3.8以上版本都可以运行这些代码不需要任何第三方库。如果你想用更规范的测试框架可以装一下pytest但初学阶段真的没必要标准库的assert完全够用。5. 个人经验怎么练双指针最有效5.1 同一个模板连续做五道题我自己练双指针时最大的感受是“模板不重要识别模型的能力才重要”。什么叫识别模型就是你看到一道新题能快速判断它属于“相向双指针”还是“同向双指针”然后才知道该往哪个方向套。练这个能力我建议用一个很笨但很有效的方法把使用同一个思路的题放在一起连续做。比如今天只练相向双指针就把“两数之和II”“回文串判断”“反转数组”“反转字符串中的单词”四道题连着做完明天只练同向双指针就把“移除元素”“删除重复项”“最长无重复子串”“长度最小的子数组”四道题连着做完。这么做的好处是你能清晰地感受到每种形态的“手感”相向双指针往往是“一大一小往中间凑”同向双指针往往是“快指针负责扫描慢指针负责维护有效区间”。做得多了看到新题就能条件反射式地归类。5.2 自己给自己出题变着花样改条件还有一个训练方法是改题。把“有序数组两数之和”改成“无序数组两数之和”你会发现哈希表更合适把“找最长无重复子串”改成“找最短覆盖所有目标字符的子串”你会发现滑动窗口的收缩策略完全不同把“判断回文串”改成“最多删除一个字符后能否成为回文”你会发现需要一次“容错”的机会两个指针不再是对称移动。我特别推荐“最多删除一个字符”这道题它表面上只是回文判断的小变体实际上考察的是你能否在指针碰撞过程中灵活地“分叉探索”。这种进阶练习会让你对双指针的边界理解上升一个台阶远胜过盲目刷几十道同类型题。最后再分享一个小心得学双指针不要只看别人的解析视频一定要亲手把代码敲出来再删掉再默写出来。我试过很多次看的时候觉得自己全懂了一合上屏幕写五分钟边界条件还是写错得离谱。只有亲手踩过那些坑这些代码才会真正变成你的工具。
双指针在Python算法题里的地位有点像炒菜时的“热锅凉油”——看似基础却决定了后面很多技巧能不能顺利展开。很多初学者学完Python基础语法后刷LeetCode第一题就开始卡壳原因往往不是不会写代码而是不知道用什么样的“遍历结构”去解决问题。双指针恰好就是那个最快见效的突破口它把很多原本需要两重循环才能搞定的问题直接砍成了一次遍历时间复杂度从O(n^2)降到O(n)空间复杂度还能保持在O(1)。这篇文章我打算用完整的Python代码示例把双指针的两种基本形态、典型应用场景、边界条件处理和排查经验一次性讲透适合正在准备算法面试的人也适合学完Python基础想做算法进阶的读者。我自己在带新人刷题时发现一个规律绝大多数人不是看不懂双指针的解法而是不知道“什么时候该用双指针”“指针该怎么移动”。这篇文章就围绕这两个核心问题展开。1. 双指针技巧的核心设计思路1.1 双指针是什么两种基本形态先给一个准确但不绕的定义双指针就是在遍历数组、字符串或链表这类线性结构时不是用一个下标或者一个节点去从头扫到尾而是用两个下标也就是两个“指针”协同配合共同完成搜索、覆盖或比较的工作。这两个指针的关系只有两种相向双指针一个指针从最左边出发一个指针从最右边出发逐步向中间靠拢。典型场景就是有序数组的二分查找变体、回文串判断、原地反转数组。同向双指针两个指针都从同一端出发但移动速度不一样。典型场景是快慢指针检测链表环、滑动窗口求最长连续子串、原地删除数组重复元素。很多资料会把滑动窗口单列出来讲但本质上滑动窗口就是同向双指针的一种变体只不过更强调“窗口”这个抽象概念。你先记住这个框架后面写代码时思路会清晰很多。这个技巧的精髓在于两个指针并不需要真正地去“指”内存地址在Python里它们通常就是整数下标。理解成两个人站在数组的不同位置各自按规则往某个方向走就对了。1.2 为什么双指针能省时间单调性带来的剪枝要想真正掌握双指针光会套模板不够必须理解它为什么能省时间否则遇到变形题还是懵。拿最经典的两数之和来说。给定一个有序数组numbers和一个目标值target要找两个数使它们的和等于target。暴力做法是两层for循环把每一对组合都试一遍时间复杂度O(n^2)。假如数组长度是10万暴力循环就需要跑约50亿次基本没法用。那为什么双指针能做到O(n)呢关键在于输入的数组是有序的这给了我们一个非常重要的性质——单调性。数组最左边是当前范围内最小的数最右边是当前范围内最大的数。设left 0right len(numbers) - 1那么current_sum numbers[left] numbers[right]就是当前范围内能取到的“最大和的最小情况”。比较current_sum和target如果current_sum等于target正好找到答案直接返回。如果current_sum小于target说明两个数总和太小了。因为numbers[right]已经是当前最大只有把left往右移动让较小的那个数变大一点总和才可能增大。此时left左侧的所有数和numbers[right]的组合都不可能等于target被一次性排除。如果current_sum大于target说明两个数总和太大了。因为numbers[left]已经是当前最小只有把right往左移动让较大的那个数变小一点总和才可能减小。此时right右侧的所有数和numbers[left]的组合也全部被排除。每次移动一个指针都会排除一整批不可能的组合。整个过程最多移动n步所以是O(n)。这就是双指针高效的核心秘密——利用单调性在一次遍历中剪掉大量无效枚举。1.3 适用场景快照什么时候优先想双指针从实际刷题经验来看下面这几类特征是双指针的“高发区”数据是数组、字符串、链表这类线性结构而且要求原地处理或者比较。题目里提到“有序”“连续”“子数组”“子串”这些关键词。暴力解法能写出来但时间复杂度明显太高需要优化掉一层循环。题目要求空间复杂度尽量低最好不要用字典、集合等额外数据结构。反过来如果数据是无序的且不排序也OK那么用哈希表往往更合适如果数据是树形结构双指针就不太适用该用递归或BFS/DFS还是得用。我一般建议初学者先把双指针和哈希表这两种思路放在一起对比学习因为它们正好覆盖了大多数数组类题目的优化方向。2. 基础形态一相向双指针专门解决有序数组问题2.1 两数之和II从暴力循环到双指针优化先看最经典的入口题。力扣上的“两数之和 II - 输入有序数组”就是一个完美的教学案例。题目要求返回两个数的下标并且下标从1开始计数。为了演示方便我按下标从0开始写你自己在做题时改一下返回值的偏移即可。def two_sum(numbers, target): left, right 0, len(numbers) - 1 while left right: current_sum numbers[left] numbers[right] if current_sum target: return [left, right] elif current_sum target: left 1 else: right - 1 return []这段代码的核心逻辑已经在1.2节解释了。这里补充几个容易出错的细节第一循环条件必须是left right而不是left right。因为题目要求找两个不同的数如果允许left right那等于同一个数自己加自己在大多数题目里是违规的而且可能返回错误答案。即使题目允许同一个元素用两次那也应该单独处理不影响这个模板。第二为什么current_sum target时移动left而不是right因为数组有序numbers[left]已经是当前区间内最小的数如果把它和最大的numbers[right]加起来都小于target那么把right往左移只会让总和更小完全没必要。这一步是整个算法“剪枝”的关键也是面试官最喜欢问的问题。第三最后return []不要漏。虽然题目保证有解但作为一个健壮的函数还是要把无解分支写清楚。2.2 回文串判断与原地反转数组相向双指针的第二个高频应用是判断回文串。回文就是正着读和倒着读一样比如racecar、上海自来水来自海上。判断的方法就是两个指针从两端往中间走一旦发现对应位置字符不相等立即返回False。def is_palindrome(s): left, right 0, len(s) - 1 while left right: if s[left] ! s[right]: return False left 1 right - 1 return True这个写法很简洁但要注意一个隐藏问题如果字符串里有空格、标点且题目要求忽略这些非字母数字字符那就需要在比较前做预处理。我一般是这样处理的def is_palindrome_alpha(s): cleaned .join(ch.lower() for ch in s if ch.isalnum()) left, right 0, len(cleaned) - 1 while left right: if cleaned[left] ! cleaned[right]: return False left 1 right - 1 return True不过预处理会额外占用O(n)空间。如果面试官要求严格的空间限制可以用while left right在循环内部跳过非字母数字字符但那样代码会复杂一点。实际工作中我倾向于先写清楚、可读性高的版本再根据需求优化。原地反转数组也是同一个套路。Python里虽然有nums.reverse()但理解底层过程仍然重要因为反转思想会迁移到很多变形题里比如字符串单词反转、旋转数组。def reverse_list(nums): left, right 0, len(nums) - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 return nums这里特别提醒Python新手nums[left], nums[right] nums[right], nums[left]这个写法在Python里是安全的它等价于用一个临时变量完成交换。在C语言或Java里你可能会写temp nums[left]; nums[left] nums[right]; nums[right] temp;但在Python里直接用多元赋值就行简洁且不易出错。2.3 相向双指针的边界哲学做相向双指针最容易翻车的地方就是循环结束的条件到底该用还是以及最后left和right相遇时指向的元素到底要不要处理。我的经验是这样的先问自己当left right时这个正中间的元素还需要比较吗判断回文串时中间元素和它自己比较没有意义所以while left right结束时不处理中间元素。反转数组时中间元素不用交换所以同样是while left right。二分查找时如果搜索区间是闭区间[left, right]那么left right时还剩下最后一个候选元素必须再判断一次所以用while left right。说白了边界条件的核心不是死记硬背而是搞清楚循环不变量每次循环开始时未被检查或未处理的数据范围是什么。只要把不变量想清楚边界就不会错。还有一个实用小技巧写完代码后用长度分别为0、1、2、3的极简输入各跑一遍。比如空数组、[1]、[1,2]、[1,2,3]人工推演一下循环过程绝大多数边界问题当场就能暴露。3. 基础形态二同向双指针覆盖快慢指针与滑动窗口3.1 快慢指针链表环检测与找中点同向双指针最典型的应用是判断链表是否有环。Floyd判圈算法大家应该都听过一个快指针每次走两步一个慢指针每次走一步如果链表里有环快指针迟早会追上慢指针并相遇如果没有环快指针会先走到链表末尾。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False这里有个细节值得展开为什么快指针每次走两步而不是走三步、四步因为慢指针每次走一步如果环的长度是L那么快指针相对慢指针的速度差是每轮一步。这意味着每经过一轮快指针离慢指针的距离就会缩短1所以最多走L轮两者必然相遇。如果速度差不是1比如快指针每次走三步那快指针相对慢指针速度差是2当环的长度为偶数时两个指针可能在环里一直交替错过虽然实际上通过数学可以证明在某些条件下也会相遇但分析起来麻烦很多。所以在判圈问题上快指针走两步、慢指针走一步是最稳妥、最容易证明的方案。顺带说一下找链表中点同样用一快一慢两个指针快指针到末尾时慢指针正好在中点位置。这个技巧在“回文链表”这类题目里很常用因为你可以先找到中点再把后半段反转然后用相向双指针比较。3.2 快慢指针做原地数组压缩同向双指针不只用在链表上数组里同样常见典型题目是“移除元素”。题目要求原地删除所有值等于val的元素返回新数组的长度。暴力做法是每删除一个元素就把后续所有元素往前移时间复杂度O(n^2)。用快慢指针可以做到一趟遍历完成def remove_element(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow这里的两个指针分别扮演什么角色fast负责从头到尾扫描原数组它像侦察兵逐个检查每个元素是否该保留。slow负责维护“有效区域”的末尾位置它像施工队把该保留的元素搬到前面的空位。每次遇到一个不等于val的元素就把它写到nums[slow]然后slow前进一格。扫描结束后nums的前slow个位置就是删除后的有效内容后面的旧数据不用管因为题目只要求前slow长度有效。这个模式的通用性很强稍微改一下判断条件就能解决“删除有序数组中的重复项”“把数组中的所有0移动到末尾”等问题。比如删除重复项的版本def remove_duplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1注意这个版本是“先移动slow再写入”因为得先给新元素腾位置。和移除元素那版的区别在于slow初始值是0还是1写入前slow是否先加1。这两个细节很容易搞混我建议你把两个函数并排放在一起对比着看自己推演一遍nums [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]这个过程。3.3 滑动窗口最长无重复子串的完整实现滑动窗口是双指针里最“实战”的内容也是面试中出现频率最高的类型之一。我直接拿“最长无重复字符的子串”这个经典题来讲。题目是这样的给定一个字符串找出其中不含有重复字符的最长连续子串的长度。比如abcabcbb答案是abc长度3。暴力思路是枚举所有起点再对每个起点不断扩展终点直到出现重复字符。每个起点都要重新扫描复杂度O(n^2)。滑动窗口版本可以用O(n)解决def length_of_longest_substring(s): last_seen {} left 0 max_len 0 for right, ch in enumerate(s): if ch in last_seen and last_seen[ch] left: left last_seen[ch] 1 last_seen[ch] right max_len max(max_len, right - left 1) return max_len我来解释这段代码为什么这么写。窗口用[left, right]表示right每轮向右扩展一个字符。last_seen字典记录每个字符最近一次出现的位置。关键分支是那句if ch in last_seen and last_seen[ch] left如果当前字符之前在窗口内出现过即last_seen[ch] left说明窗口已经“不合法”了需要把left跳到该字符上次出现位置的下一个位置把重复字符排挤出去。如果当前字符之前出现过但位置在left左边说明那个旧位置已经被移出窗口了当前字符在新窗口里没有冲突不用动left。为什么要判断last_seen[ch] left因为如果不判断遇到s abba这种情况就会出错。我们跑一下right0字符aleft0记录last_seen{a: 0}max_len1。right1字符bleft0记录last_seen{a: 0, b: 1}max_len2。right2字符blast_seen[b]1 left0所以left 1 1 2更新last_seen[b]2窗口长度2-211max_len保持2。right3字符alast_seen[a]0但注意last_seen[a]0不再大于等于left2说明这个a在旧位置已经被甩出了当前窗口当前窗口里并没有a所以left不动。窗口长度3-212max_len保持2。如果去掉last_seen[ch] left这个判断第4步就会把left误设为last_seen[a] 1 1导致窗口变成[1, 3]错误地认为找到了长度3的无重复子串bba。这个坑几乎每个初学者都会踩一次。4. 实战中的常见问题与排查技巧4.1 边界条件速查表写双指针题边界条件往往是运行时错误的重灾区。我把常见场景整理成一张速查表你写之前扫一眼能少走很多弯路。输入情况典型处理方式常出问题的点空数组或空字符串函数开头直接返回空结果或0nums[0]索引越界长度为1的数组根据题意判断是否需要特殊处理循环条件写错导致直接进不了循环所有元素都相同快慢指针能否正确推进slow的初始值写错返回值差1目标值不存在循环结束后要有默认返回值忘记return []或return -1负数参与比较有序性依然成立双指针照常用拿绝对值大小做判断逻辑混淆链表为空或只有一个节点判环和找中点都要提前处理fast.next.next触发空指针异常比如回文判断空字符串按定义是回文很多人的代码在s 时会直接索引越界正确的做法是先判断if len(s) 1: return True。这种“防御性写法”在算法面试里很加分因为面试官能看到你考虑问题是否周全。4.2 死循环与越界的几个经典现场我在自己调试和帮人review代码时遇到最多的问题就是死循环和越界。这里分享几个真实翻车现场。第一个死循环案例某个同学写两数之和时循环体里只写了判断和更新却没有在current_sum target时返回结果永远卡在那个分支里。这种问题倒好办跑一遍测试用例看哪个样例无法结束加一行print(left, right)立刻就能定位。第二个越界案例链表判环时很多人会写成while fast.next and fast.next.next但忽略了一开始的while fast and fast.next。当fast本身已经是None时再访问fast.next会直接抛AttributeError。正确做法是先把fast本身是否为None判断掉。第三个逻辑疏忽案例相向双指针的循环里先移动指针还是先比较值顺序不能乱。比如反转数组必须在交换后再同时移动两个指针。如果你在某一轮只移动了一个指针下一次循环条件就可能产生错位导致交换错元素。我调试时最常用的方法是在关键循环里临时加print(left, right, nums[left], nums[right])手动运行两三轮对照手推结果。很多看似玄学的bug用这个方法五分钟就能定位。在LeetCode上跑不通的时候别急着怀疑编译器先把样例缩到最小自己走一遍。4.3 在本地快速验证双指针代码的小建议很多刚配好Python环境的朋友喜欢把代码直接贴到在线评测系统里跑失败了再一遍遍提交这样效率其实很低。我建议你在本地写几个断言把核心测试用例一次性跑完。比如刚才的最长无重复子串可以这样写assert length_of_longest_substring(abcabcbb) 3 assert length_of_longest_substring(bbbbb) 1 assert length_of_longest_substring(pwwkew) 3 assert length_of_longest_substring() 0 assert length_of_longest_substring(au) 2 print(all tests passed)用assert的好处是一旦某个用例不通过程序会立即终止并标明是哪一行。我要强调一下本地写测试断言不是浪费时间恰恰是最快的学习方式。它能帮你在短时间内跑大量输入把边界条件和循环不变量彻底吃透。至于环境本身Python 3.8以上版本都可以运行这些代码不需要任何第三方库。如果你想用更规范的测试框架可以装一下pytest但初学阶段真的没必要标准库的assert完全够用。5. 个人经验怎么练双指针最有效5.1 同一个模板连续做五道题我自己练双指针时最大的感受是“模板不重要识别模型的能力才重要”。什么叫识别模型就是你看到一道新题能快速判断它属于“相向双指针”还是“同向双指针”然后才知道该往哪个方向套。练这个能力我建议用一个很笨但很有效的方法把使用同一个思路的题放在一起连续做。比如今天只练相向双指针就把“两数之和II”“回文串判断”“反转数组”“反转字符串中的单词”四道题连着做完明天只练同向双指针就把“移除元素”“删除重复项”“最长无重复子串”“长度最小的子数组”四道题连着做完。这么做的好处是你能清晰地感受到每种形态的“手感”相向双指针往往是“一大一小往中间凑”同向双指针往往是“快指针负责扫描慢指针负责维护有效区间”。做得多了看到新题就能条件反射式地归类。5.2 自己给自己出题变着花样改条件还有一个训练方法是改题。把“有序数组两数之和”改成“无序数组两数之和”你会发现哈希表更合适把“找最长无重复子串”改成“找最短覆盖所有目标字符的子串”你会发现滑动窗口的收缩策略完全不同把“判断回文串”改成“最多删除一个字符后能否成为回文”你会发现需要一次“容错”的机会两个指针不再是对称移动。我特别推荐“最多删除一个字符”这道题它表面上只是回文判断的小变体实际上考察的是你能否在指针碰撞过程中灵活地“分叉探索”。这种进阶练习会让你对双指针的边界理解上升一个台阶远胜过盲目刷几十道同类型题。最后再分享一个小心得学双指针不要只看别人的解析视频一定要亲手把代码敲出来再删掉再默写出来。我试过很多次看的时候觉得自己全懂了一合上屏幕写五分钟边界条件还是写错得离谱。只有亲手踩过那些坑这些代码才会真正变成你的工具。
的贡献法优化思维)
