双指针技术

双指针（Two Pointers）是数组、字符串、链表上最常用的算法技巧之一。它用一个看似平凡的细节–用两个游标代替一个游标遍历–换取指数级的效率提升。表面上看，从「单指针 O(n²)」到「双指针 O(n)」省下的是一次嵌套循环；往深处理解，双指针真正在做的是利用问题本身的结构（单调性、有序性、区间不变量），把搜索空间裁剪成一个低维流形。

这一篇我们系统地拆解双指针的四大家族：对撞指针、快慢指针、前后指针、滑动窗口。每一类对应一种「游标间的相对运动方式」，背后是一种「搜索空间裁剪策略」。读完本文，你应该能在面对一道新题时迅速判断：这题适合哪种双指针？正确性靠什么不变量保证？边界如何处理？

一、引言：从暴力到双指针

1.1 一个朴素的例子

考虑经典问题：「给定一个升序整数数组 nums 和目标值 target，返回和为 target 的两个元素的下标（下标从 1 开始）。」

暴力做法是对所有数对枚举：

#include <vector>
using namespace std;

// 暴力：O(n^2)
vector<int> twoSumBrute(vector<int>& nums, int target) {
    int n = (int)nums.size();
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (nums[i] + nums[j] == target)
                return {i + 1, j + 1};
    return {};
}

这版代码做了 O(n²) 次比较。但是「升序」这一条件被完全忽略了。能否利用有序性裁剪搜索空间？

1.2 双指针的直觉

令 left = 0，right = n - 1，比较 nums[left] + nums[right] 与 target：

若和偏小，说明左边的元素太小，left++ 让和变大；
若和偏大，说明右边的元素太大，right-- 让和变小；
若相等，返回。

#include <vector>
using namespace std;

// 双指针：O(n)
vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return {left + 1, right + 1};
        else if (sum < target) ++left;
        else --right;
    }
    return {};
}

为什么这样做正确？关键在于「有序性」赋予了搜索空间一个单调结构：固定 left 时，right 越大，和越大。所以一旦 nums[left] + nums[right] < target，对当前 left 而言，任何 right' < right 都只会让和更小，全部排除。这正是双指针的本质–用一次比较 O(1) 地排除一整行（或一整列）候选。

我们把这张「候选对」铺成 n×n 的上三角矩阵，暴力枚举要遍历整个三角；双指针则从右上角出发，每一步要么向左、要么向下，走出一条单调路径，长度至多 2n。O(n²) → O(n) 的根源就在这里。

二、核心思想与正确性直觉

2.1 什么是双指针

「双指针」并非特指某一种算法，而是一类技巧的统称。它们的共同点是：在序列上维护两个游标 i、j（或 slow/fast、left/right），游标按某种规则协同推进，从而把 O(n²) 的暴力枚举压缩成 O(n) 的线性扫描。

游标协同的方式不同，就衍生出不同的子家族：

子家族	游标运动方向	典型问题	关键不变量
对撞指针	相向（left→ ←right）	有序两数之和、盛水容器	区间 [left, right] 始终包含待考虑候选
快慢指针	同向，速度不同	链表环、找中点、倒数第 k	快慢间距 / 相遇点蕴含位置信息
前后指针	同向，分读写	移除元素、去重	[0, slow) 维护已写入结果
滑动窗口	同向，定长或不定长	最小覆盖子串、最长无重复子串	[left, right] 始终满足某约束

2.2 正确性的两大支柱

无论哪种双指针，正确性都依赖两个支柱：

支柱一：不变量（Invariant）。每一步操作前后，某个关于 [left, right]（或 [0, slow)）的命题始终成立。比如对撞两数之和中，「待检查的候选对全在 [left, right] 内」就是不变量。不变量保证算法不会漏解。

支柱二：单调性（Monotonicity）。游标推进的方向能让我们「朝目标靠近」而不走回头路。比如有序两数之和，left++ 必然让和增大，right-- 必然让和减小–单调性保证算法不会陷入死循环，且每步都排除一批无效候选。

💡 判断一道题能不能用双指针，先问自己两个问题：
我能定义一个不变量，使「当前未排除的候选」始终位于某个区间内吗？
序列的单调性（天然的或排序后的）能让我每步排除「一整片」候选吗？
两个都能答「是」，双指针多半能拿下。

2.3 复杂度优化的本质

很多人对双指针的理解停留在「省了一层循环」。这只说对了一半。更精确的说法是：

暴力枚举遍历的是「候选集合」本身，规模通常是 O(n²) 甚至更高；
双指针遍历的是「候选集合的边界」，借助单调性把内部候选批量排除，规模降到 O(n)。

形象地说，双指针不是「跳过了一些候选」，而是「用一次决策就判定了整个一维切片」。这种「降维」式的剪枝是双指针的精髓，也解释了为什么排序常常是双指针的前置步骤–排序的本质是给数据建立单调结构，而双指针是单调结构上最高效的扫描器。

三、算法框架与模板

在具体例题之前，先把四种双指针的骨架抽象出来。后面所有题目都是这四个模板的变体。

3.1 对撞指针模板

int left = 0, right = n - 1;
while (left < right) {          // 或 left <= right，依题意
    if (满足条件) {
        // 记录答案 / 处理
        ++left; --right;        // 或只动一边
    } else if (需要更大) {
        ++left;                 // 让值变大
    } else {
        --right;                // 让值变小
    }
}

适用场景：序列有序（天然或排序后），目标是找满足某条件的「两端组合」。复杂度 O(n)。

3.2 快慢指针模板（链表）

ListNode *slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    // slow 走 1 步，fast 走 2 步
}
// slow 现在指向中点（或前半段末尾）

适用场景：链表上一次遍历获取位置信息（中点、环、倒数第 k）。复杂度 O(n)。

3.3 前后指针模板（同向，读写分离）

int slow = 0;                          // 写指针：[0, slow) 是已写入结果
for (int fast = 0; fast < n; ++fast) { // 读指针：扫描每个元素
    if (nums[fast] 满足保留条件) {
        nums[slow++] = nums[fast];
    }
}
return slow;  // 新长度

适用场景：原地修改数组，保留满足条件的元素（去重、过滤）。复杂度 O(n)，空间 O(1)。

3.4 滑动窗口模板（不定长）

int left = 0, ans = 0;
某种数据结构 window;          // 维护窗口状态
for (int right = 0; right < n; ++right) {
    window.add(s[right]);     // 右端入窗
    while (窗口不合法) {       // 收缩到合法
        window.remove(s[left]);
        ++left;
    }
    ans = max(ans, right - left + 1);  // 更新答案
}

适用场景：在连续子区间上求满足约束的最值。复杂度 O(n)（每个元素入窗、出窗各一次）。

💡 滑动窗口的核心技巧：右端永远只前进（for 循环），左端只在「窗口不合法」时收缩（while 循环）。两者都单调前进，故总操作 O(n)。

接下来用一系列例题把这些模板填满。

四、对撞指针

对撞指针（也叫相向双指针）的标志是两个游标从序列两端相向而行，每次根据当前状态决定移动哪一端。它最依赖「单调性」–没有单调性，相向移动就毫无意义。

4.1 两数之和 II（有序数组）

给定升序数组 nums 和目标 target，返回和为 target 的两元素下标（1-based）。答案唯一。

这正是开篇的例子，这里给出完整可编译版本并补充变种。

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = (int)numbers.size() - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1};  // 题目要求 1-based
            } else if (sum < target) {
                ++left;   // 和偏小，左端右移让和变大
            } else {
                --right;  // 和偏大，右端左移让和变小
            }
        }
        return {};  // 题目保证有解，不会走到
    }
};

复杂度：时间 O(n)，空间 O(1)。相比暴力 O(n²) 或哈希 O(n) 空间，对撞指针在「有序 + 空间敏感」的场景最优。

正确性论证：维护不变量「所有未排除的候选对 (i, j) 都满足 i >= left 且 j <= right」。初始时 left=0, right=n-1，不变量成立。每一步：

若 nums[left] + nums[right] < target，对当前 left，任何 j < right 的和更小，全部排除，故 left++ 安全；
若 > target，对当前 right，任何 i > left 的和更大，全部排除，故 right-- 安全；
若相等，直接返回。

不变量始终成立，且若解存在必在 [left, right] 内，故必能找到。

变种：若数组无序，可先排序再用对撞指针，整体 O(n log n)；若要求返回原下标，则排序会丢失原下标，需要用「值-下标」对排序，或退回到哈希法。

4.2 盛最多水的容器

给定非负整数数组 height，每个元素表示竖直线段高度。两条线段与 x 轴围成的容器容积 = min(height[i], height[j]) * (j - i)。求最大容积。

这道题没有「有序」条件，但有一个隐藏的单调结构：宽度 j - i 随双指针相向移动而单调减小。这让我们能用对撞指针。

思路：初始化 left=0, right=n-1，此时宽度最大但高度受限两端较矮者。每一步把较矮的一端向内移动一格–因为移动较高的一端不可能让容积变大（高度仍受较矮端限制，宽度却变小了），只有移动较矮端才有可能遇到更高的线、突破瓶颈。

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = (int)height.size() - 1;
        int ans = 0;
        while (left < right) {
            // 容积 = 较矮高度 × 宽度
            int h = min(height[left], height[right]);
            int w = right - left;
            ans = max(ans, h * w);
            // 移动较矮的一端：只有它变高才可能突破当前瓶颈
            if (height[left] < height[right]) {
                ++left;
            } else {
                --right;
            }
        }
        return ans;
    }
};

复杂度：时间 O(n)，空间 O(1)。

正确性论证：设当前两端 left、right，height[left] <= height[right]。对任意 k 满足 left < k < right，候选 (left, k) 的容积 <= height[left] * (k - left) <= height[left] * (right - left)，即不大于当前 (left, right) 的容积。因此固定 left 时，所有以 left 为左端的候选都不会更优，可以安全排除，left++ 不会丢失最优解。height[left] > height[right] 时对称。

这道题把对撞指针的「排除一整片」思想发挥到极致：每次排除的不是「一行」而是「以较矮端为锚的一整片候选」。

变种：若题目改为「三条线段围成的最大容积」（类似三数之和），可固定一端 + 对撞两端，复杂度 O(n²)。

4.3 三数之和（双指针 + 排序）

给定数组 nums，返回所有和为 0 的不重复三元组。

这是双指针与排序配合的经典案例。暴力枚举 O(n³) 不可接受。思路：先排序 O(n log n)，然后固定第一个数 nums[i]，对剩余区间 [i+1, n) 用对撞指针找两数之和等于 -nums[i]，整体 O(n²)。

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = (int)nums.size();
        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] > 0) break;             // 最小值已 >0，不可能凑出 0
            if (i > 0 && nums[i] == nums[i - 1]) continue;  // 跳过重复的第一个数
            int left = i + 1, right = n - 1;
            int target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    // 跳过重复的 left / right
                    while (left < right && nums[left] == nums[left + 1]) ++left;
                    while (left < right && nums[right] == nums[right - 1]) --right;
                    ++left; --right;
                } else if (sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
        return ans;
    }
};

复杂度：时间 O(n²)，空间 O(log n)（排序栈空间）。

关键技巧：去重。固定 i 时跳过与上一轮相同的 nums[i]；找到一组解后跳过与左右端相同的相邻值。去重必须在「确认当前值有效之后」进行，否则会漏解。

为什么排序后能用双指针：排序建立了单调性，固定 i 后子问题「在 [i+1, n) 找两数和为 -nums[i]」退化为 4.1 的标准对撞指针。

4.4 接雨水（对撞指针，最优解）

给定柱子高度数组，求能接多少雨水。

经典的双指针解法。思路：每个位置能接的水量 = min(左侧最大值, 右侧最大值) - 自身高度（若为正）。朴素做法预计算左右最大值数组，O(n) 时间 O(n) 空间。双指针版能压到 O(1) 空间。

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int n = (int)height.size();
        if (n == 0) return 0;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            // 较矮的一端是瓶颈，该端可立即结算水量
            if (height[left] < height[right]) {
                ans += leftMax - height[left];  // 必为非负
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};

复杂度：时间 O(n)，空间 O(1)。

正确性：关键洞察是–当 height[left] < height[right] 时，leftMax 已经反映了 [0, left] 的最大值，而由于 height[right] 更高，右端必然存在一个 >= height[left] 的挡板，所以 left 处的水位由 leftMax 决定，可以立即结算。对称同理。这正是对撞指针「用一端的信息立即推算该端答案」的典范。

五、快慢指针

快慢指针（Floyd’s Tortoise and Hare）最常用于链表。两个游标同向而行，但速度不同，速度差会转化为位置信息–相遇意味着环存在，速度比决定了相遇点的几何意义。

5.1 检测链表环（原文示例）

下面是合并版原文的代码，我们保留它并补全注释。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;
    
    ListNode *slow = head;
    ListNode *fast = head->next;
    
    while (fast && fast->next) {
        if (slow == fast) return true;
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

复杂度：时间 O(n)，空间 O(1)。

正确性直觉：若有环，fast 比 slow 每步多走 1 步，相对速度为 1。在环内，每步两者距离减 1，必然在有限步内追上（相遇）；若无环，fast 先到达 nullptr。

为什么 slow 起点设 head、fast 设 head->next：让初始状态就 slow != fast，避免循环一开始就误判为「相遇」。也可以都设 head，循环条件改成 do-while 或先走一步。

5.2 找环的入口

更进阶的问题：若有环，找出环的入口节点。

Floyd 算法分两阶段：

快慢指针找到相遇点；
让一个指针回到 head，两指针同速前进，再次相遇处即环入口。

证明：设环外长度 a，环长度 b，相遇时 slow 走了 s 步，fast 走了 2s 步。fast 比 slow 多走的 s 步一定是 b 的整数倍（绕了若干圈）：s = k * b。又 s = a + x（x 是相遇点在环内偏移），故 a + x = k * b，即 a = k * b - x。从 head 走 a 步到环入口，等于从相遇点走 k * b - x 步（绕 k 圈减偏移）也到环入口。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return nullptr;
        ListNode *slow = head, *fast = head;
        // 第一阶段：判断是否有环并找到相遇点
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                // 第二阶段：一指针回 head，同速再走
                ListNode *p = head;
                while (p != slow) {
                    p = p->next;
                    slow = slow->next;
                }
                return p;  // 环入口
            }
        }
        return nullptr;  // 无环
    }
};

复杂度：时间 O(n)，空间 O(1)。

5.3 找链表中点

快慢指针的另一经典应用：一次遍历找到链表中点。fast 走 2 步、slow 走 1 步，fast 到末尾时 slow 恰在中点。这是归并排序链表版的前置步骤。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 返回中点；偶数长度时返回前半段的最后一个节点
ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

细节：循环条件 fast->next && fast->next->next 让偶数长度时 slow 落在「前半段末尾」（下取整中点），适合「断开链表做归并」。若改成 fast && fast->next，偶数时 slow 落在「后半段首」（上取整中点）。两种写法差一格，依下游用途选择。

复杂度：时间 O(n)，空间 O(1)。

5.4 删除倒数第 k 个节点

给定链表，删除倒数第 k 个节点。

朴素做法：先遍历求长度 n，再正向走到第 n-k 个节点。两趟遍历。双指针一趟搞定：让 fast 先走 k 步，然后 slow 与 fast 同速前进；fast 到末尾时，slow 恰在倒数第 k+1 个（即待删节点的前驱）。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int k) {
        ListNode dummy(0);          // 哨兵，统一处理删除头节点的情况
        dummy.next = head;
        ListNode *fast = &dummy, *slow = &dummy;
        // fast 先走 k+1 步，使 slow 最终落在待删节点的前驱
        for (int i = 0; i <= k; ++i) {
            fast = fast->next;
        }
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* toDelete = slow->next;
        slow->next = slow->next->next;  // 跳过待删节点
        delete toDelete;
        return dummy.next;
    }
};

关键技巧：哨兵节点 dummy。它消除「删除头节点」这一特例–没有 dummy 时若 k 恰为链表长度，需要单独处理。引入哨兵后所有删除操作形式统一。

复杂度：时间 O(n)，空间 O(1)。

变种：若只需求「倒数第 k 个节点的值」（不删除），让 fast 先走 k 步即可，无需哨兵。

5.5 快慢指针的数学本质

快慢指针家族的精髓是「用速度差编码位置信息」。设快指针速度 v_f、慢指针速度 v_s，运行时间 t 后：

位置差 = (v_f - v_s) * t；
在链表（无环）上，位置差直接对应「快指针比慢指针多走的节点数」；
在环上，位置差对环长取模后稳定收敛到 0（相遇）。

选择 v_f = 2, v_s = 1（相对速度 1）是最常见的，因为「相对速度 1」保证在环内每步距离减 1，必相遇。若选 v_f = 3, v_s = 1（相对速度 2），可能「跳过」相遇点（环长为偶数时），需更谨慎。实践中几乎总用 2:1。

六、前后指针（同向读写分离）

前后指针（也叫同向双指针、读写双指针）的两个游标同向而行，分工明确：fast（读指针）扫描每个元素，slow（写指针）只在「需要保留」时写入。它专门用于原地修改数组，把「保留满足条件的元素」压缩成 O(n) 时间 O(1) 空间。

6.1 移除元素

给定数组 nums 和值 val，原地移除所有等于 val 的元素，返回新长度。

#include <vector>
using namespace std;

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;  // 写指针：[0, slow) 是保留下来的元素
        for (int fast = 0; fast < (int)nums.size(); ++fast) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];  // 保留并写入
            }
            // 等于 val 的元素被 fast 跳过，不写入
        }
        return slow;  // 新长度
    }
};

复杂度：时间 O(n)，空间 O(1)。

不变量：循环任意时刻，[0, slow) 是已扫描部分中「不等于 val」的元素序列。fast 每前进一步，若当前元素合格，就追加到 slow 处。结束时 [0, slow) 即结果。

为什么这是双指针而非单指针：因为 slow 和 fast 是两个独立游标。fast 永远 >= slow，差距等于「已跳过的不合格元素数」。这种「读写分离」是同向双指针的标志。

6.2 删除有序数组中的重复项

升序数组，原地删除重复元素，使每个元素只出现一次，返回新长度。

#include <vector>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int slow = 1;  // 写指针：[0, slow) 已去重；首元素必保留
        for (int fast = 1; fast < (int)nums.size(); ++fast) {
            // 升序：与上一个保留元素不同即为新元素
            if (nums[fast] != nums[slow - 1]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

复杂度：时间 O(n)，空间 O(1)。

关键：利用「升序」–重复元素必相邻，故只需比较 nums[fast] 与 nums[slow-1]（上一个写入的元素）。若无序，需先排序或用哈希。

变种：允许重复两次（保留每个元素最多两次）：

int removeDuplicatesII(vector<int>& nums) {
    if ((int)nums.size() <= 2) return (int)nums.size();
    int slow = 2;  // 前两个元素必保留
    for (int fast = 2; fast < (int)nums.size(); ++fast) {
        // 与 slow-2 比较：允许至多两个相同
        if (nums[fast] != nums[slow - 2]) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

把 slow - 1 改成 slow - 2，逻辑立刻从「保留一次」变成「保留两次」。这是模板的可扩展性体现。

6.3 移动零

给定数组，把所有 0 移到末尾，保持非零元素相对顺序，原地操作。

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;  // 下一个非零元素应写入的位置
        for (int fast = 0; fast < (int)nums.size(); ++fast) {
            if (nums[fast] != 0) {
                swap(nums[slow++], nums[fast]);  // 交换而非覆盖
            }
        }
    }
};

复杂度：时间 O(n)，空间 O(1)。

与 6.1 的区别：6.1 用「覆盖」丢弃 val，本题用「交换」把 0 换到后面。覆盖会丢失被覆盖位置的 0 信息，交换则保留所有元素。选覆盖还是交换，取决于是否需要保留被跳过的元素。

6.4 前后指针的通用模板

观察 6.1-6.3，它们都符合一个模式：

int slow = 起始写位置;
for (int fast = 起始读位置; fast < n; ++fast) {
    if (nums[fast] 满足保留条件) {
        // 写入 slow（覆盖或交换）
        nums[slow] = nums[fast];  // 或 swap(nums[slow], nums[fast]);
        ++slow;
    }
}

只要能形式化为「扫描 + 条件保留 + 原地写入」的问题，都能套这个模板。

七、滑动窗口

滑动窗口（Sliding Window）是同向双指针的高级形态：维护一个区间 [left, right]（窗口），右端不断扩张，左端按约束收缩。它适合所有「在连续子区间上求满足约束的最值」问题。

7.1 不定长滑动窗口模板

不定长窗口的核心结构已在 3.4 给出，这里再强调一遍「四步法」：

右端入窗：window.add(s[right])，扩展窗口；
判断合法性：检查窗口是否仍满足约束（如「字符频次足够」「无重复」「和不超过 k」）；
左端收缩：若不合法，循环 window.remove(s[left]); ++left; 直到合法；
更新答案：合法状态下用窗口大小更新最优解。

关键不变量：循环每次回到「合法」状态时，窗口 [left, right] 是「以 right 为右端的最长合法窗口」中的一种（求最长时）或「以 right 为右端的最短合法窗口」（求最短时）。所有「以 right 为右端的合法子区间」都通过 left 的收缩被遍历到。

7.2 最小覆盖子串（原文示例）

下面是合并版原文的代码，我们保留它并补全注释。

#include <string>
#include <unordered_map>
#include <climits>

std::string minWindow(std::string s, std::string t) {
    std::unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0;
    int start = 0, len = INT_MAX;
    
    while (right < s.size()) {
        char c = s[right++];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        
        while (valid == need.size()) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            char d = s[left++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}

复杂度：时间 O(|s| + |t|)，空间 O(|字符集|)。

算法解读：

need 记录 t 中每个字符的需求量，window 记录当前窗口内对应字符的计数；
valid 记录「已满足需求的字符种类数」，当 valid == need.size() 时窗口覆盖了 t；
外层 while 扩展右端；内层 while 在「已覆盖」时尝试收缩左端并记录最小窗口。

为什么 valid 用「种类数」而非「字符数」：避免 window[c] 超过 need[c] 时误增 valid。只有 window[c] == need[c]（恰好满足）时才增 valid，超过不再增；收缩时只有从「恰好满足」降到「不足」才减 valid。这是滑动窗口计数的经典技巧。

变种：

若 t 含重复字符，本代码已正确处理（need 是计数而非集合）；
若问「最长覆盖子串」（窗口最长而非最短），把内层 while 改为 if（只收缩一次），并在合法时更新答案即可。

7.3 无重复字符的最长子串

给定字符串 s，找不含重复字符的最长子串长度。

#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> window;
        int left = 0, ans = 0;
        for (int right = 0; right < (int)s.size(); ++right) {
            // 右端字符已存在窗口内：收缩到不重复
            while (window.count(s[right])) {
                window.erase(s[left]);
                ++left;
            }
            window.insert(s[right]);
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

复杂度：时间 O(n)，空间 O(字符集)。

对比 7.2：7.2 是「窗口需满足某条件，求最短」，内层用 while 收缩到「恰好不满足」再停；本题是「窗口需满足某条件，求最长」，内层用 while 收缩到「重新满足」即停。求最短 → 收缩到不合法；求最长 → 收缩到合法。这是滑动窗口方向选择的口诀。

优化：用 unordered_map<char, int> 记录每个字符的最新下标，遇到重复时直接把 left 跳到「重复字符上次出现 + 1」，省去内层 while。但语义上仍是滑动窗口，只是「跳跃式收缩」。

#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

int lengthOfLongestSubstringOpt(string s) {
    unordered_map<char, int> last;  // 字符 -> 最新下标
    int left = 0, ans = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        char c = s[right];
        if (last.count(c) && last[c] >= left) {
            left = last[c] + 1;  // 跳跃式收缩
        }
        last[c] = right;
        ans = max(ans, right - left + 1);
    }
    return ans;
}

注意 last[c] >= left 的判断–若重复字符在 left 之前，已被排除出窗口，无需收缩。

7.4 定长滑动窗口与「翻转最多 k 个 0」

给定 0/1 数组和整数 k，可翻转最多 k 个 0，求最长连续 1 子数组长度。

这其实是不定长窗口的变体–约束是「窗口内 0 的个数 <= k」。

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, zeros = 0, ans = 0;
        for (int right = 0; right < (int)nums.size(); ++right) {
            if (nums[right] == 0) ++zeros;
            while (zeros > k) {            // 0 太多，收缩
                if (nums[left] == 0) --zeros;
                ++left;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

复杂度：时间 O(n)，空间 O(1)。

真正的「定长」窗口：若题目固定窗口大小 k（如「长度为 k 的子数组最大和」），用更简单的模板，左端跟着右端同步前进，不需要 while 收缩：

#include <vector>
using namespace std;

// 长度为 k 的子数组的最大和
int maxSumFixed(vector<int>& nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; ++i) sum += nums[i];  // 初始化第一个窗口
    int ans = sum;
    for (int i = k; i < (int)nums.size(); ++i) {
        sum += nums[i] - nums[i - k];            // 右端进、左端出
        ans = max(ans, sum);
    }
    return ans;
}

定长窗口只需维护一个「滑动的和」（或哈希、单调队列），左端跟着右端同步前进。

7.5 滑动窗口最大值（单调队列配合）

给定数组和窗口大小 k，返回每个窗口的最大值。

这是滑动窗口 + 单调队列的经典组合。普通窗口维护最大值需 O(nk)；用单调队列（双端队列，存候选最大值的下标）降到 O(n)。

#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> dq;  // 存下标，对应值单调递减
        for (int right = 0; right < (int)nums.size(); ++right) {
            // 1. 新元素入队前，弹出队尾所有比它小的（它们不可能再当最大值）
            while (!dq.empty() && nums[dq.back()] <= nums[right]) dq.pop_back();
            dq.push_back(right);
            // 2. 队首超出窗口范围，弹出
            if (dq.front() <= right - k) dq.pop_front();
            // 3. 窗口形成后，队首即最大值
            if (right >= k - 1) ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};

复杂度：时间 O(n)（每个元素入队出队各一次），空间 O(k)。

单调队列的本质：维护一个「有资格成为最大值的候选」序列。新元素入队时，比它小的旧元素永远不可能再成为最大值（新元素既更大又更晚出窗），直接淘汰。这正是双指针「用一次比较排除一片候选」思想的延伸–只不过这里借助了双端队列这个数据结构。

八、横向对比

把四类双指针放在一起对比，看清它们的边界。

维度	对撞指针	快慢指针	前后指针	滑动窗口
游标方向	相向	同向（速度不同）	同向（速度相同）	同向
适用结构	有序数组	链表	数组（原地修改）	数组/字符串
关键不变量	候选全在 [left,right]	速度差编码位置	[0,slow) 是结果	窗口满足约束
典型问题	两数之和、盛水容器	环检测、找中点	去重、移除元素	子串、子数组和
时间复杂度	O(n)	O(n)	O(n)	O(n)
空间复杂度	O(1)	O(1)	O(1)	O(字符集) 或 O(k)
是否需排序	常需	不需	常需（去重类）	不需
代码形态	while + if/else	while 速度差	for + if	for + while

选择口诀：

看到「有序 + 两端凑值」→ 对撞；
看到「链表 + 位置/环」→ 快慢；
看到「原地修改 + 保留条件」→ 前后；
看到「连续子区间 + 约束」→ 滑动窗口。

复杂度统一为 O(n) 的原因：四类双指针的共同点是「两个游标都单调前进，每个元素至多被处理常数次」。这是双指针族最深刻的共性–通过单调性保证线性。

九、双指针与排序的配合

排序是双指针最常见的「前置处理」。许多问题在无序状态下无法直接双指针，排序后立即获得单调性，双指针就能上场。但排序也带来代价：O(n log n) 时间、丢失原下标、去重需求。

9.1 何时排序

求值不求下标：如三数之和、最接近的三数之和–排序不损失信息；
求下标：如两数之和（返回原下标）–排序会丢失原下标，需存「值-下标」对，或退用哈希；
需去重：排序后重复元素相邻，便于跳过；
要求结果有序：排序一举两得。

9.2 排序 + 双指针 vs 哈希

以两数之和为例，三种解法对比：

解法	时间	空间	适用
暴力	O(n²)	O(1)	n 很小
哈希	O(n)	O(n)	无序、需原下标
排序 + 双指针	O(n log n)	O(1) 或 O(n)	有序、空间敏感

经验：若数组已有序，双指针是首选（O(n) 时间 O(1) 空间）；若无序且需原下标，哈希更直接；若无序但只求值，排序 + 双指针省空间。

9.3 排序 + 前后指针（去重）

6.2 的「删除有序数组重复项」就是排序 + 前后指针的典型。若数组无序，先排序 O(n log n)，再用前后指针去重 O(n)，整体 O(n log n)；若不能改变顺序，则需用哈希 O(n) 空间。

9.4 排序 + 对撞指针的延伸：N 数之和

三数之和（4.3）的框架可推广到 N 数之和：排序 + 递归固定前 N-2 个数 + 最内层对撞指针，复杂度 O(n^(N-1))。这是「排序建立单调性、双指针利用单调性」思想的极致运用。

#include <vector>
#include <algorithm>
using namespace std;

// 四数之和：排序 + 两层固定 + 对撞指针，O(n^3)
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = (int)nums.size();
        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;  // 去重
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;  // 去重
                int left = j + 1, right = n - 1;
                // 注意 target 可能很大，用 long long 避免溢出
                long long need = (long long)target - nums[i] - nums[j];
                while (left < right) {
                    long long sum = nums[left] + nums[right];
                    if (sum == need) {
                        ans.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) ++left;
                        while (left < right && nums[right] == nums[right - 1]) --right;
                        ++left; --right;
                    } else if (sum < need) {
                        ++left;
                    } else {
                        --right;
                    }
                }
            }
        }
        return ans;
    }
};

注意四数之和中 target 可能超出 int 范围，求和时必须用 long long，这是大数场景下双指针的常见陷阱。

十、实战场景

10.1 竞赛中的双指针

双指针在算法竞赛中是「必备工具」，常出现在：

CF Div2 A/B 题：贪心 + 双指针的简单题，如区间合并、配对问题；
LeetCode 周赛：滑动窗口几乎每场必考；
NOIP/CSP：链表快慢指针、有序数组对撞是基础题。

竞赛技巧：

先想暴力再优化：写出 O(n²) 暴力，观察哪些候选能批量排除，往往自然导出双指针；
画图找单调性：在纸上画出候选矩阵，看能否走出单调路径；
哨兵简化边界：链表题几乎总要加 dummy 节点；
while vs if：求最短用 while（收缩到不合法），求最长用 if（只收缩一次）或不收缩。

10.2 工程中的应用

双指针不仅是面试题，工程中也常见：

流式数据去重：日志/事件流去重，前后指针模板直接可用（前提是数据有序或可缓存窗口）；
网络包重组：滑动窗口是 TCP 流控的核心机制之一，工程实现与算法模板同构；
数据库归并：归并排序的合并阶段是对撞指针；外排序的归并段合并也是；
文本处理：编辑器的「查找不重复最长片段」、IDE 的「括号匹配」都可滑动窗口化；
限流算法：滑动窗口限流（Fixed Window / Sliding Window）直接对应定长滑动窗口模板。

10.3 双指针的工业变体

在推荐系统、广告匹配中，常有「在两个有序候选池中找满足某约束的配对」–这正是对撞两数之和的工业版。例如：

用户特征池与商品特征池匹配，找相似度最高的前 K 对；
两个时间序列的对齐（DTW 简化版）。

这些场景下，双指针的 O(n) 复杂度比嵌套循环 O(n²) 在大规模数据上节省可观算力。

十一、常见陷阱与边界条件

11.1 越界与空指针

对撞指针：left < right 还是 left <= right？多数「找两数」用 <（避免重合）；「二分式」可能需 <=；
链表快慢指针：fast && fast->next 必须同时检查，否则 fast->next->next 解引用空指针；
空数组/单元素：所有模板都应在入口判断 n < 2 提前返回。

11.2 去重的位置

三数之和（4.3）的去重是高频陷阱：

错误：在 while 进入时就跳过所有相同值–会漏解；
正确：找到一组解后再跳过相邻相同值，或在固定 i 时跳过与 i-1 相同的值（外层去重）。

去重的口诀：「先记录答案，再跳相邻」。

11.3 滑动窗口的 `while` vs `if`

求最短合法窗口：用 while 持续收缩到「不合法」，记录最后一次合法状态；
求最长合法窗口：用 while 收缩到「合法」即停（或用 if 只收缩一次，依赖右端扩张）；
混淆二者是滑动窗口最常见 bug。

11.4 窗口状态维护

入窗和出窗必须对称：window.add(x) 对应 window.remove(x)，频次/计数必须严格配对，否则 valid 会失真；
用 unordered_map 时注意「计数归零后是否 erase」–不 erase 也行，但判断条件要改成 window[c] >= need[c] 而非 window.count(c)。

11.5 链表哨兵的取舍

删除头节点场景必须用 dummy；
只读场景（找中点、判环）不需要 dummy；
dummy 用栈对象 + .next 指针，避免手动 new/delete 的内存管理负担。

11.6 整数溢出

盛水容器、接雨水涉及面积/水量乘法，int 可能溢出，注意 long long；
两数之和的 sum 在数值很大时也可能溢出，用 long long 比较；
四数之和（9.4）中 target 本身可能超 int，必须用 long long 接收。

11.7 排序的稳定性

若需保留原下标，排序会丢失信息，需用「值-下标」对；
不稳定排序（如 std::sort）可能打乱相同值的相对顺序，去重时无所谓，但「保留前 k 个」类问题需注意。

11.8 快慢指针起点不一致

5.1 中 slow = head、fast = head->next 是为了让初始 slow != fast。若都从 head 出发且用 while (slow != fast)，第一次判断就为真，会误判有环。起点与循环条件的搭配必须自洽：要么错开起点，要么用 do-while。

十二、小结

双指针技术的核心是用两个协同游标替代暴力枚举，借助单调性与不变量把搜索空间从高维压到一维。它的四大家族对应四种游标协同方式：

对撞指针利用有序性，从两端相向裁剪候选；
快慢指针利用速度差，在链表上编码位置信息；
前后指针利用读写分离，原地过滤数组；
滑动窗口利用区间不变量，在连续子区间上求最值。

它们共享一个深层结构：两个游标都单调前进，每个元素至多被处理常数次，故复杂度统一为 O(n)。这种「线性时间处理二次候选」的能力，是双指针在算法工具箱中不可替代的原因。

掌握双指针的关键不在记忆模板，而在理解每种模板背后的不变量与单调性。面对新题，先问自己：候选空间是什么形状？哪里有单调性？能定义什么不变量？三个问题答清，模板自然浮现。

最后给出一张「题目 → 双指针类型」的速查表，供刷题时对照：

题目	类型	关键不变量
两数之和 II（有序）	对撞	候选在 [left,right]
盛最多水的容器	对撞	较矮端为瓶颈
三数之和	排序 + 对撞	固定一端后子问题对撞
接雨水	对撞	较矮端可立即结算
链表环检测	快慢	相对速度 1 必相遇
找环入口	快慢	Floyd 两阶段
链表中点	快慢	2:1 速度比
删除倒数第 k	快慢	fast 先走 k 步
移除元素	前后	[0,slow) 是结果
删除重复项	前后	与 slow-1 比较
移动零	前后	交换保留信息
最小覆盖子串	滑动窗口	valid == need.size
最长无重复子串	滑动窗口	窗口内无重复
滑动窗口最大值	窗口 + 单调队列	队列单调递减

刷题时把这张表当索引，遇到新题先归类，再套模板，最后抠边界。双指针的题量大但套路集中，掌握这十几道代表题，足以应付绝大多数变体。

一、引言：从暴力到双指针

1.1 一个朴素的例子

1.2 双指针的直觉

二、核心思想与正确性直觉

2.1 什么是双指针

2.2 正确性的两大支柱

2.3 复杂度优化的本质

三、算法框架与模板

3.1 对撞指针模板

3.2 快慢指针模板（链表）

3.3 前后指针模板（同向，读写分离）

3.4 滑动窗口模板（不定长）

四、对撞指针

4.1 两数之和 II（有序数组）

4.2 盛最多水的容器

4.3 三数之和（双指针 + 排序）

4.4 接雨水（对撞指针，最优解）

五、快慢指针

5.1 检测链表环（原文示例）

5.2 找环的入口

5.3 找链表中点

5.4 删除倒数第 k 个节点

5.5 快慢指针的数学本质

六、前后指针（同向读写分离）

6.1 移除元素

6.2 删除有序数组中的重复项

6.3 移动零

6.4 前后指针的通用模板

七、滑动窗口

7.1 不定长滑动窗口模板

7.2 最小覆盖子串（原文示例）

7.3 无重复字符的最长子串

7.4 定长滑动窗口与「翻转最多 k 个 0」

7.5 滑动窗口最大值（单调队列配合）

八、横向对比

九、双指针与排序的配合

9.1 何时排序

9.2 排序 + 双指针 vs 哈希

9.3 排序 + 前后指针（去重）

9.4 排序 + 对撞指针的延伸：N 数之和

十、实战场景

10.1 竞赛中的双指针

10.2 工程中的应用

10.3 双指针的工业变体

十一、常见陷阱与边界条件

11.1 越界与空指针

11.2 去重的位置

11.3 滑动窗口的 while vs if

11.4 窗口状态维护

11.5 链表哨兵的取舍

11.6 整数溢出

11.7 排序的稳定性

11.8 快慢指针起点不一致

十二、小结

11.3 滑动窗口的 `while` vs `if`