双指针算法复盘总结：从元素思维到边界思维

核心主题：从”元素思维”转向”边界思维”。

刷双指针的题,最大的坎不是不熟悉模板,而是身份认知的问题:你总把指针当成”当前元素的下标”,但它实际上是”区域的边界”。这篇复盘把双指针完整分类、每类的区域定义与不变式、错题解剖、防错检查单整理成一份可复用笔记。

一、双指针完整分类地图

双指针
├── 同向（两个指针朝同一方向走）
│   ├── 快慢指针：速度不同，fast探路，slow守家
│   └── 滑动窗口：距离动态变化，right扩张找可行解，left收缩找最优解
│
├── 对向（两个指针从两头往中间走）
│   ├── 对撞指针：left←————→right，直到相遇
│   └── 三指针/荷兰国旗：对撞 + 中间加侦察兵i
│
└── 分离（两个指针在两条数组/链表上）
    └── 分离双指针：各走各的，谁小谁移动

面试核心就三类：快慢指针、对撞指针、滑动窗口。荷兰国旗是对撞的扩展。

二、每类指针的”区域定义”与不变式

2.1 快慢指针（Fast & Slow）

本质：fast 在未知区探路，slow 标记有效区边界。

区域图：

[ 有效区 ) [ 废弃/未知区 )
0       slow        fast         n

不变式：[0, slow) 永远是处理好的有效区，slow 是”下一个待写入位置”（不是最后一个有效元素的下标）。

代码骨架：

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (nums[fast] 满足条件) {
        nums[slow] = nums[fast];  // 先写入边界位置
        slow++;                   // 再扩界
    }
}
return slow;  // slow就是有效区长度

致命易错点：

• 必须先 nums[slow] = ... 再 slow++，不能反过来
• slow 是”边界/长度”，不是”下标”

2.2 对撞指针（Two Pointers from Both Ends）

本质：left 和 right 从两头往中间挤，利用有序性或对称性。

区域图：

[ 已排除 ) [ 待处理 ] [ 已排除 )
0        left     right         n-1

不变式：[0,left) 和 (right,n-1] 是已处理/已排除区，[left,right] 是待处理区。

代码骨架：

int left = 0, right = n - 1;
while (left < right) {  // 注意是 <，不是 <=
    if (条件满足) left++;
    else if (另一条件) right--;
    else { left++; right--; }
}

2.3 滑动窗口（Sliding Window）

本质：快慢指针的变体。right 扩张找”可行解”，left 收缩找”最优解”。

窗口是连续区域 [left, right)。整套算法的节奏只有三个动作，每个动作各回答一个问题——记清楚这三个问题，模板就不会写乱。

① 什么时候扩张 right？加入字符时更新什么数据？

扩张是默认动作：right 是”读指针”，每个字符都必须被它看过一次，所以外层循环每轮无条件走一步。真正要判断的不是”什么时候扩张”，而是”什么时候停止扩张”——信号不在扩张侧，而在收缩侧：一旦加入字符后窗口状态翻转，就暂停扩张，转入收缩（两种题型的”翻转信号”正好相反，见 ③ 的表）。

窗口加入字符时，更新的是记账数据（window state）——描述”窗口现状”的变量，不是答案：

规则：扩张 = 入账。入账只改状态，不碰答案。

② 什么时候暂停扩张、开始收缩 left？移出字符时更新什么数据？

收到”翻转信号”后，while 收缩：移出 s[left] → 更新记账 → left++，直到窗口达到目标状态（最长型：重新合法；最短型：即将非法）。

窗口移出字符时，更新同一套记账数据，方向与入账严格相反：

规则：收缩 = 销账，与入账严格对称——从哪个字符入的账，移出它时就要原样退回。

关键：收缩必须是 while 不是 if——移出一个字符可能仍不满足条件，需要连续收缩。

③ 答案在哪里更新？——最长型 vs 最短型

候选解必须是”合法窗口”，所以答案只在窗口合法的时刻更新。 但”合法时刻”落在哪一侧，决定了两种题型的写法——这是滑动窗口唯一需要分类的地方：

口诀：最长型在”恢复合法”时取 max，最短型在”维持合法”时取 min。

反例验证（为什么不能乱放）：

• max 放在扩张时 → 把非法窗口（含重复字符 / 超过 K 个 distinct）也算进去，答案虚高
• min 放在收缩循环外 → 循环退出时窗口已经非法，最小值永远取不到

两种题型，同一副骨架：

// 最长型：收缩条件 = 非法，更新在收缩循环之后（合法出口）
int left = 0, right = 0, ans = 0;
while (right < n) {
    add(nums[right]);            // 扩张：入账
    right++;
    while (窗口非法) {            // 缩到重新合法
        remove(nums[left]);      // 收缩：销账
        left++;
    }
    ans = max(ans, right - left);   // 合法时刻（出口）：取 max
}

// 最短型：收缩条件 = 合法，更新在收缩循环之内（每个合法瞬间）
int left = 0, right = 0, ans = INT_MAX;
while (right < n) {
    add(nums[right]);            // 扩张：入账
    right++;
    while (窗口合法) {            // 缩到即将非法
        ans = min(ans, right - left);   // 合法时刻（体内）：取 min
        remove(nums[left]);      // 收缩：销账
        left++;
    }
}

走一遍（无重复字符最长子串，s = “abcabcbb”）：

• right=0、1、2：依次入账 a、b、c → 窗口合法 → 出口取 max → ans = 1 → 2 → 3
• right=3：入账 a → 频次 a 变 2 → 窗口非法 → 收缩：销掉 s[0]=’a’ → 重新合法（left=1，窗口 “bca”）→ 出口取 max(3, 2) = 3
• 全程节奏：入账 → 可能非法 → 销账到合法 → 出口取 max

走一遍（最小覆盖子串，LeetCode 76——最短型的完整代码）：

想找「覆盖 t 的最短子串」，用的正是最短型骨架，和上面的模板一一对照：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;        // need：t 的需求清单

        int left = 0, right = 0;
        int valid = 0;                     // 已「数量凑齐」的字符种类数
        int start = 0, len = INT_MAX;      // 答案：起始下标 + 长度

        while (right < s.size()) {
            char c = s[right];             // ① 即将入窗口的字符
            right++;                       //    扩张（默认动作）
            if (need.count(c)) {           //    入账：只记 need 关心的字符
                window[c]++;
                if (window[c] == need[c]) valid++;  // 这种字符凑齐了，种类数 +1
            }

            while (valid == need.size()) { // ② 合法 = 每种字符都凑齐 → 收缩
                if (right - left < len) {  // ③ 最短型：在收缩循环内更新 min
                    start = left;          //    （每步都合法，且越缩越短）
                    len = right - left;
                }
                char d = s[left];          // ② 即将出窗口的字符
                left++;                    //    收缩
                if (need.count(d)) {       //    销账：对称退回
                    if (window[d] == need[d]) valid--;  // 减之前先判断（减完就不够了）
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

valid 的计数技巧：valid 不是「覆盖了几个字符」，而是「数量恰好凑齐」的字符种类数。入账时数量刚好到 need[c] 就 valid++；销账时这个字符在移出前数量刚好等于 need[d]，移出后就差一个，所以先 valid-- 再 window[d]--。这一收一放，正是 ② 里说的「入账销账严格对称」，也把 ② 表格里「已覆盖 target 的字符数」这一行落到了实处。

一句话收束：入账（扩张）只改状态，销账（收缩）对称退回，答案只在”合法”的瞬间诞生——最长型诞生在缩回合法的出口，最短型诞生在维持合法的体内。

2.4 荷兰国旗（三指针 / Dutch National Flag）

本质：对撞指针的扩展，处理”3 类元素原地三分区”。

区域图（必须刻进 DNA）：

[0, left)     → 0区（已搞定）
[left, i)     → 1区（已搞定）
[i, right]    → 未知区（待探索）
(right, n-1]  → 2区（已搞定）

不变式：i 是未知区的左边界，right 是未知区的右边界。i 绝对不可以踏入 (right, n-1] 这个已完工的 2 区。

代码骨架：

int left = 0, right = n - 1, i = 0;
while (i <= right) {  // 关键：未知区是[i,right]，不是[0,n)
    if (nums[i] == 0) {
        swap(nums[i], nums[left]);
        left++; i++;        // 换过来的是1（来自1区），安全
    } else if (nums[i] == 1) {
        i++;                // 1就在中间，不动
    } else { // nums[i] == 2
        swap(nums[i], nums[right]);
        right--;            // i不动！换过来的来自未知区，必须再检查
    }
}

致命易错点：

• 循环条件必须是 i <= right，绝不能是 i < n
• swap 2 时 i 绝对不能动

2.5 分离双指针

本质：两个指针在两个数组上，协作而非竞争。

铁律：谁小谁移动，相等时一起移动。

三、错题解剖

3.1 Remove Duplicates（保留最多 k 个重复）

错误代码：

int slow = 0;
unordered_map<int,int> check;  // 错误1：不需要HashMap
for(int fast = 0; fast < nums.size(); fast++) {
    if(check[fast]!=check[slow] && check[nums[fast]]<2) {  // 错误2：索引和值混用
        slow++;              // 错误3：先移动
        nums[slow]=nums[fast]; // 再写入，导致偏移
        check[nums[fast]]++;
    }
}
return slow+1;  // 错误4：返回slow+1来弥补偏移

错误根因：

1. 没利用”有序数组”特征：有序数组去重不需要 HashMap，直接和边界比
2. slow 语义错误：把 slow 当成”最后一个有效元素下标”，实际上 slow 是”下一个待写入位置”
3. 写入顺序错误：必须先 nums[slow] = ... 再 slow++

正确通用模板（保留 k 个重复）：

int removeDuplicates(vector<int>& nums, int k) {
    int n = nums.size();
    if (n <= k) return n;
    int slow = k;  // 前k个无条件保留
    for (int fast = k; fast < n; fast++) {
        if (nums[fast] != nums[slow - k]) {  // 和有效区倒数第k个比（警戒线）
            nums[slow] = nums[fast];  // 先写入
            slow++;                   // 再扩界
        }
    }
    return slow;  // 边界就是长度
}

3.2 Sort Colors（荷兰国旗）

错误代码：

while(i < nums.size()) {  // 致命错误
    if(nums[i]==0) { swap(nums[slow],nums[i]); slow++; i++; }
    else if(nums[i]==1) { i++; }
    else { swap(nums[i],nums[fast]); fast--; }
}

错误根因：

• 循环条件错误：用了 i < n，导致 i 冲进已经排好的 2 区，把 2 又 swap 回中间
• 没理解区域定义：i 不是”遍历整个数组的游标”，而是”未知区的左哨兵”；fast 右边是已完工区，禁止踏入

正确代码：

while (i <= fast) {  // 未知区是[i,fast]
    if (nums[i] == 0) { swap(nums[i], nums[slow]); left++; i++; }
    else if (nums[i] == 1) { i++; }
    else { swap(nums[i], nums[fast]); right--; /* i不动 */ }
}

3.3 其他常见错误模式

四、核心根因：”元素思维” vs “边界思维”

你总把指针当成”当前元素的下标”，但它实际上是”区域的边界”。

一句话总结：写代码时脑子里想的是”这个元素怎么处理”，但双指针要求你想的是”这个区域怎么变化”。

为什么容易混淆？

这是非常正常的编程思维惯性：

• 平时写 for (int i = 0; i < n; i++)，i 就是”当前元素”
• 但双指针里，slow / left / i 往往是左闭右开区间的右边界
• 这个转变是反直觉的，所以你会用 slow+1 去”修正”，用 i < n 去”遍历”

slow+1 和 i < n 不是代码错误，是”身份认知错误”的补丁。 补丁打多了，逻辑就乱了。

五、防错检查单

写代码前必须回答：

• 我画出了区域图吗？（[搞定区) ptr [待处理区) ptr [搞定区]）
• 每个指针是”位置”还是”边界”？（边界 = 指向区域外第一个元素）
• 循环条件是从”待处理区是否为空”推导的吗？
• 指针移动后，区域定义还成立吗？
• 返回的是边界（长度）还是下标？

六、一句话决策树

看到"原地修改/分区" + "一个数组"
    │
    ├─ 找连续子串/子数组的最长最短 → 滑动窗口
    ├─ 3类固定值原地三分区 → 荷兰国旗（left/i/right）
    ├─ 有序数组 + 去重/分区 → 快慢指针（slow/fast）
    └─ 两头往中间凑 → 对撞指针（left/right）

看到"两个数组/链表"找关系
    └─ 分离双指针（谁小谁走）

七、核心口诀

两类对撞挤，三类荷兰旗；
换零两边走，换二右边缩；
中间是净土，遇一直接过。
slow是边界，先写再扩界；
i是侦察兵，只逛未知区。

补充口诀：

“怕覆盖，就倒着填；两头大，取一边；同方向，快慢走。”

八、关键认知转变

8.1 数组是廉价的，思维是昂贵的

总想原地操作（insert、直接覆盖），是因为觉得”开新数组浪费空间”。但算法题里：

• O(n) 额外空间是常规操作
• 破坏原始数据才是致命错误

下次拿到数组题，先问自己：“我能不能倒着填？能不能开个新数组？” 如果答案是可以，大概率这就是正解。

8.2 进步轨迹

对比第一题和难题（对角线排序）：

• 第一题：insert 导致长度爆炸，逻辑完全失控
• 难题：已经会利用数学特征做分组，会用 back() + pop_back() 优雅回填

难题的难度其实更高，但核心逻辑写对了。这说明不是不会双指针，只是还没习惯”从后往前”和”另开数组”这两个 trick。

九、练习建议

9.1 每日必做：看到数组题，先画两个箭头

• 箭头从两端往中间走 → 对向双指针（平方和、两数之和）
• 箭头从后往前走 → 逆向双指针（合并、替换空格）
• 一快一慢往右走 → 快慢双指针（移除元素、链表判环）

画 5 分钟箭头，再写代码。代码写对了，再把箭头擦掉。

9.2 专项突破计划

1. 接下来 3 天，只做快慢指针和荷兰国旗，不碰滑动窗口和对撞
2. 每道题强制画区域图，用 [ ) 符号标出”已搞定区”和”未知区”
3. 写代码前，先口头解释：slow 是下标还是边界？i 能踏进 right 右边吗？
4. 允许自己开新数组，先放弃”原地修改”的执念，把逻辑跑通再优化

9.3 画区域图的正确姿势

错误画法（直觉）：
[1, 1, 2, 2, 3]
    ↑
   slow（指向1）

正确画法（双指针语义）：
[1, 1) [2, 2, 3)
      ↑
     slow（边界，指向2）

把指针画成”栅栏”而不是”箭头”。

十、边界认知自测题

数组 [1,1,1,2,2,3]，保留最多 2 个重复，用快慢指针。

1. 初始时 slow 应该等于几？
2. fast 从几开始？
3. 第一次满足 nums[fast] != nums[slow-2] 时，slow 指向的位置会发生什么？

正确答案：

1. slow 初始是 2（前 2 个无条件保留，边界停在第 3 个位置）
2. fast 从 2 开始探路
3. 第一次满足条件时，nums[slow] = nums[fast]，然后 slow++ 扩界

如果第一反应是 slow=1、fast=0、先 slow++ 再赋值 → 身份认知还没转过来，需要再练。

十一、更高纬度：双指针到底在干嘛

前面十节是”术”，这一节是”道”。学会之后，你看到的不再是三道题，而是一个原理的三个投影。

11.1 为什么双指针都是 O(n)：单调前沿扫描

暴力做法是在 O(n²) 的 (i,j) 配对上找答案。双指针做的事从来不是”扫得聪明”，而是：证明绝大多数配对永远不可能是答案，然后永久丢髥它们。

每个指针单调移动（永不回头）→ 每个指针总共只走 O(n) 步 → 摊还 O(n)。

剩下的候选解排成一条单调阶梯（staircase）——l 每前进一步，对应的 r 只往一个方向动。沿着这条阶梯走一遍就是 O(n)。滑动窗口、对撞、分离，全是这个图景，区别只是那条前沿长什么样。

11.2 指针移动 = 支配证明

把 l++ / r-- 从”移动变量”重命名为”删除候选解集”：

“我删掉了所有以当前 l（或 r）为界的候选解，并证明它们不可能最优。”

接雨水那道题：leftMax < rightMax 时 left 的水量被左墙锁死，右边再高也救不了这个位置——所以以它为左界的全部候选解都是死的，可以理直气壮地 left++。每次移动前问一句：”我删掉了什么，凭什么？” 答不上来的移动，就是靠背模板在写。

11.3 “双指针”其实是三个家族

宽度上记住三张面孔，别再当一个东西背：

两个彩蛋：荷兰国旗本质是三路划分 = quicksort 3-way partition 的内核；归并那道题本质是归并排序的 merge 步骤。你刷的每道双指针，都是在单练排序/检索里切出来的一刀。

11.4 数组型快慢 = 读写分离流水线

忘掉”快慢”，改叫”读写”：fast 是读指针（唯一信息源，必须遍历每个元素），slow 是写指针（有效区边界）。

fast (迭代器，读) → [ 过滤规则 ] → slow (输出流，写)

这是 in-place 版的 filter 流水线，输出流和输入流在同一个数组上重叠。真正的问题只有一个：什么时候原地安全？

写指针永远不能越过尚未读取的数据源。

正向写（去重/移除，写 ≤ 读）安全；结果比源长时必须倒着填（Merge Sorted Array、替换空格），从尾部空白缓冲区出发——正写和反写是同一枚硬币，方向反转只是为了让写指针继续躲着源走。别再纠结”开新数组是不是浪费”，画两个箭头问：“这样写我会踩到还没读的元素吗？”

11.5 决策所需的最小状态量（错题一的最终解释）

第三章的错题一，当时说是”有序数组不需要 HashMap”。现在可以讲透：区别是做一次留/删决策，最少要记住多少东西。

关键的表述：有序性把”全局支配”压成”局部支配”。移除元素是全局恒真命题（值本身决定去留，不依赖任何前缀）；去重依赖历史。有序后，相同的值被迫相邻——”这个值出现过几次”的完整历史坍缩成一个下标（slow-k 哨兵）。排序没有替你推导，排序让记忆降维成指针。

11.6 这架电梯还能升到别的题

“结构单调 → 决策状态可压缩 → 摊还 O(n)”不止双指针：滑动窗口 while 收缩、单调栈每个元素进出一次、KMP 失配回退有界，全是同一架电梯的不同楼层。

下次做题别只问”这题是不是双指针”，改问：“这题的决策，最少的必要记忆是什么？” 答案是常数 ⇒ 存在一趟流水的做法；答案必须是全部历史 ⇒ 要么排序/建结构把它压下来，要么这题就吃定 O(n) 空间。

十二、通俗版专项：对撞指针的”瓶颈锁定额水”

第十一章讲了道，这一章把对撞家族里的”瓶颈锁死型”（盛水、接雨水）用最舒服的方式再讲一遍——全部浓缩成一个原理：木桶效应，瓶颈锁定额水。

12.1 核心原理：矮的是天花板

不管盛水还是接雨水，全篇只有一句话：水能存多少，由矮的那边决定。

这是木桶效应——杯壁再高也没用，水从矮的那边溢出去。所以”矮墙 = 天花板”，谁矮谁定水。

12.2 盛最多水：矮墙淘汰（最单纯的版本）

一排墙，选两堵当杯壁，装水量 = 矮的那堵墙的高度 × 两墙距离。双指针从最左和最右开始（距离最大），每轮都”淘汰”对里比较矮的那堵墙。

为什么淘汰矮的？把道理说得特别白：

左边这堵墙矮。把它留着，右边换任何一堵墙——宽度只会更窄（右边只能往左挪），水量天花板永远是矮的那边的高度。所以这堵矮墙跟谁配都赢不了，直接枪毙它这一整列候选。

注意这个动作不是”试试别的”，而是一次性判死刑：以矮墙为边的所有组合都不可能超过当前这对——因为当前这对的宽度已经拉满（两端最远），矮墙又封了顶。这个角度上已经到达它的人生巅峰，往里走埋伏更高墙去了。

12.3 接雨水：同一个原理，搬到每个坑上

接雨水麻烦一点：水不是装在选定的两堵墙之间，而是积在每一格坑里，左右都得有墙才存得住水。每个格子能存多少，公式一句话：

水量 = min(左边最高的墙, 右边最高的墙) − 我这格的高度

还是木桶效应：左边最高墙 5、右边最高墙 8，水面最多到 5（从矮那边流走），减去坑深 1，存 4 格水。

难点：每个坑都要”左右最高的墙”，难道每个坑都往左右扫一遍（O(n²)）？双指针的笨办法变聪明之处——从两头往中间边走边记，只记两个数：

leftMax  = 左指针一路走来见过的墙里最高的
rightMax = 右指针一路走来见过的墙里最高的

现在盯住左指针脚下的格子，要做判断：它右边到底有没有够高的墙？

这里是最容易卡住的一步，请勾重点：

rightMax 不是”右边那堵墙有多高”，而是”右边这一路已经看过的墙里最高的”。右边那片还没看过的区域里，真正的右最高只会比 rightMax 高（或持平），绝不可能更矮。

所以可以放心地说一句：右边至少有一堵 rightMax 这么高的墙。

判断就清脆了：

• leftMax < rightMax → 右边保证有比 leftMax 更高的墙 → 右边当不了瓶颈 → 瓶颈就是 leftMax → 这格水量 = leftMax − 自己，定死，左指针往前走
• 反过来，右边一格的积水量被 rightMax 锁定，右指针往前走

12.4 一张表收尾：淘汰 vs 锁定，都是木桶效应

慢节奏上手建议：在纸上随便画一排墙的高度数组，用手模拟 leftMax / rightMax 从左到右蠕动一遍，每个格子停下来算一次——走完一遍，代码自然就默写得出来了。

总结

不是不会双指针，是还没习惯”用边界思考，而不是用元素思考”。

这个转变没有捷径，但每次写代码前问一句 “这个指针是箭头，还是栅栏？”，一周之内就能彻底改过来。

好算法往往是反直觉的，而直觉正在被慢慢修正。 这个过程就叫学习。