双指针数组题学习笔记

学习网址：https://labuladong.online/zh/algo/essential-technique/array-two-pointers-summary/

数组双指针看起来题很多，但真正常用的思路其实没有那么多。把题目按方法拆开，基本就是三类：快慢指针、滑动窗口、左右指针。它们表面上都在用两个下标，实际解决的问题却完全不同。

快慢指针主要解决原地修改数组的问题。像删除元素、数组去重、压缩有效元素，本质上都是一边遍历、一边把该保留的内容写回前面。最适合记住的口诀是：快指针探路，慢指针写入。 快指针负责检查当前元素，慢指针负责维护结果区间。这个方法能稳定成立，关键在于慢指针只往“已经被快指针验证过的位置”写，所以整个过程虽然是原地覆盖，但逻辑上始终安全。

滑动窗口更适合处理连续子串、子数组这类问题，常见复杂度可以做到O(N)。不过它最难的地方从来不是代码模板，而是条件设计：窗口什么时候扩大，什么时候缩小，什么时候更新答案。很多人以为滑动窗口难在双指针，其实真正难的是你是否先定义清楚窗口里维护了什么状态。双指针只是形式，区间状态才是核心。

左右指针则更强调“方向”。如果两个指针从头尾向中间逼近，通常是在利用有序性或区间性质，比如二分查找、n 数之和、反转数组；如果从某个位置向两端扩展，通常是在利用对称性，比如回文串判断。它的重点不是扫一遍数组，而是通过移动方向不断缩小答案范围，或者验证结构是否成立。

所以，双指针真正该记住的，不是几套固定代码，而是三种不同任务：快慢指针负责写结果，滑动窗口负责控区间，左右指针负责逼答案。 一旦把这三件事分开，很多数组题的思路都会清楚很多。

快慢指针最适合处理数组里的“原地修改”问题。比如删除指定元素、数组去重、把满足条件的元素压缩到前面，本质上都不是要开一个新数组，而是要在原数组上完成筛选和重写。

这里最实用的理解方式是这一句：快指针探路，慢指针写入。

快指针负责遍历数组，判断当前元素是否应该保留；慢指针负责把应该保留的元素写到正确的位置。这样扫完一遍之后，慢指针左边的区域，就是处理完成后的有效结果。

这个技巧能成立，关键不在“一个快一个慢”，而在于一个更底层的事实：快指针已经检查过的位置，才允许慢指针去写。 也就是说，慢指针写入的区域，始终是“已经被确认安全的区域”。一旦这个不变量想清楚，很多原地修改题都会稳定很多。

二、滑动窗口：本质不是双指针，而是维护一个区间状态

如果说快慢指针擅长处理“数组重写”，那滑动窗口更擅长处理“连续区间”问题，尤其是字符串和子数组问题。像最长无重复子串、最小覆盖子串、长度最短的子数组，这一类题都属于窗口模型。

它的时间复杂度通常能做到 O(N)，关键原因不是技巧有多神秘，而是左右边界都只单向移动，每个元素最多进窗口一次、出窗口一次。

滑动窗口真正难的地方，往往不在于代码形式，而在于两个判断：

第一，什么时候扩大窗口；第二，什么时候缩小窗口。

再往下一层，还有第三个问题：什么时候更新答案。

所以滑动窗口不是一个“固定模板”，而是一种区间控制思维。你需要先把题目翻译成窗口语言：窗口里维护的是什么状态，窗口满足什么条件算合法，不合法时该收缩到什么程度，合法时是否立刻更新结果。详细细节将单独在滑动窗口的学习笔记讲解。

三、左右指针：重点不是快慢，而是“方向感”

这一类可以分成两种典型方向。

一种是相向指针。两个指针分别从数组头尾出发，逐步向中间靠拢。这类写法非常适合那些答案能通过“夹逼”确定的题目。二分查找是典型代表，因为每次都能排除一半区间；n 数之和里的双指针部分也是类似逻辑，本质上是利用有序性，通过左右夹逼缩小搜索空间；反转数组也是同一种动作，只不过目标从“找值”变成了“交换”。

另一种是相背指针。它通常从中间某个位置出发，然后向两边扩展，更适合做对称性判断。回文串判断就是最典型的例子：不是从头尾不断排除，而是围绕某个中心检验两边是否一致。针对最长子回文串问题，原文中给出的解法是遍历每个字符，对每个字符使用相背指针找出对应的最长回文串，时间复杂度是O(N^2)。

本章涉及的题目