# 双指针、滑动窗口与对撞指针

**双指针（Two Pointers）**是一种核心的算法优化思想。它通过在数据结构（尤其是数组、链表和字符串）上设置两个或多个“指针”（通常为代表数组下标的整型变量或迭代器），并根据特定规则相向或同向移动，从而在一次遍历的过程中解决问题。
这种方法能将原本可能是平方级别 $O(N^2)$ 的双重循环暴力枚举，优雅地优化到线性级别 $O(N)$。

根据指针的移动方向与速度，双指针算法通常分为以下三大流派：
1. **快慢指针（同向双指针）**：两个指针都从起点出发，以不同的步长同向向前移动。常用于检测链表环路、寻找链表中点或删除有序数组中的重复项。
2. **滑动窗口（尺取法）**：同向双指针的一种特定策略。两个指针维护一个具有特定属性的“窗口” $[l, r]$，右指针不断向右扩展，左指针在状态不满足约束时向右收缩，用于解决连续子数组或子串的最值、计数等问题。
3. **对撞指针（左右指针）**：两个指针分别位于序列的左右两端，向中间相向移动，直至相遇。常用于有序数组的双数之和、回文判定以及容器盛水等问题。

---

## 一、 快慢指针（Fast & Slow Pointers）

快慢指针通常在一个序列上使用两个速度不同的指针：慢指针 `slow`（一般每次向前移动 1 步）和快指针 `fast`（一般每次向前移动 2 步）。利用这种相对速度差，可以高效探测序列中的特定拓扑结构。

### 1.1 环形链表检测（Floyd 判环算法）
* **题意概括**：
  给定一个链表的头节点 `head`，判断链表中是否存在环（即某个节点的 `next` 指针指向了其前面的历史节点）。

* **算法对比**：
  * **哈希表法**：遍历链表并用哈希表（`std::unordered_set`）存储访问过的节点指针，若遇到已存在的指针则说明有环。时间复杂度 $O(N)$，空间复杂度 $O(N)$。
  * **快慢指针法**（Floyd's Cycle-Finding Algorithm）：时间复杂度 $O(N)$，**空间复杂度优化至 $O(1)$**。

* **相对速度原理解析**：
  设慢指针 $s$ 每次走 1 步，快指针 $f$ 每次走 2 步。
  1. **无环情况**：$f$ 必然先到达链表末尾（`nullptr`），程序结束。
  2. **有环情况**：
     当 $s$ 刚进入环内时，设 $f$ 领先 $s$ 的距离为 $k$，环的物理周长为 $L$。
     在环内运动时，两指针的相对运动速度为：
     $$\text{相对速度} = v\_f - v\_s = 2 - 1 = 1 \quad \text{（步/次）}$$
     这意味着每次移动，$f$ 会缩短与 $s$ 之间的距离 1 个单位。因此，移动 $k$ 次后，两指针必然会在环内重合相遇（即 $f == s$），证明有环。

```cpp
#include <iostream>
using namespace std;

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

// 判断链表是否有环
bool hasCycle(Node *h) {
    if (!h || !h->next) {
        return false; // 空链表或单节点链表不可能有环
    }
    Node *s = h;
    Node *f = h;
    while (f && f->next) {
        s = s->next;       // 慢指针走 1 步
        f = f->next->next; // 快指针走 2 步
        if (s == f) {      // 相遇则证明存在环
            return true;
        }
    }
    return false; // 快指针顺利触底，无环
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // 构造带环链表: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (环入口为 3)
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    Node* n5 = new Node(5);
    n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n5;
    n5->next = n3; // 形成环

if (hasCycle(n1)) {
        cout << "Cycle detected.\n";
    } else {
        cout << "No cycle.\n";
    }
    return 0;
}
```

---

### 1.2 寻找链表中点
* **题意概括**：
  给定一个单链表的头节点 `head`，找到并返回其中间节点。若链表长度为偶数，则返回第二个中间节点。

* **快慢指针逻辑**：
  快指针 $f$ 和慢指针 $s$ 均初始化为头节点。
  $s$ 每次走 1 步，$f$ 每次走 2 步。由于速度是 2 倍关系，当 $f$ 触及末尾时，$s$ 走过的路径长度刚好是 $f$ 的一半，因此 $s$ 所在位置恰好是链表的中间节点。
  * **奇数长度 (1->2->3->4->5)**：
    * 初始: $s=1, f=1$ $\to$ 运行1: $s=2, f=3$ $\to$ 运行2: $s=3, f=5$（$f->next$ 为空终止），$s=3$ 为中点。
  * **偶数长度 (1->2->3->4->5->6)**：
    * 初始: $s=1, f=1$ $\to$ 运行1: $s=2, f=3$ $\to$ 运行2: $s=3, f=5$ $\to$ 运行3: $s=4, f=nullptr$（终止），$s=4$ 为第二个中点。

```cpp
#include <iostream>
using namespace std;

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

// 寻找并返回链表中点
Node* findMid(Node *h) {
    Node *s = h;
    Node *f = h;
    while (f && f->next) {
        s = s->next;
        f = f->next->next;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // 构造链表 1 -> 2 -> 3 -> 4 -> 5
    Node* n1 = new Node(1);
    n1->next = new Node(2);
    n1->next->next = new Node(3);
    n1->next->next->next = new Node(4);
    n1->next->next->next->next = new Node(5);

Node* mid = findMid(n1);
    if (mid) {
        cout << "Middle node value: " << mid->val << "\n"; // 输出 3
    }
    return 0;
}
```

---

## 二、 滑动窗口（Sliding Window）

滑动窗口通过左指针 $l$ 和右指针 $r$ 维护一个动态区间 $[l, r]$。窗口随着指针的右移在序列上滑动，核心在于：**“右指针无脑右移扩展，左指针有条件右移收缩”**。

### 2.1 长度最小的子数组
* **题意概括**：
  给定一个含有 $n$ 个正整数的数组 $a$ 和一个正目标值 $t$。找出数组中满足其区间元素和 $\ge t$ 的**长度最小**的连续子数组，并返回其长度。若不存在则返回 0。

* **滑动窗口机制**：
  1. 初始化 $l = 0, r = 0$，窗口内累加和 `sum = 0`，最小长度记录为极大值 `INT_MAX`。
  2. **扩展窗口**：移动右指针 $r$，累加新数据 `sum += a[r]`。
  3. **收缩窗口**：只要当前窗口满足条件（`sum >= t`），说明找到了一个可行解：
     * 尝试更新最小长度：`minLen = min(minLen, r - l + 1)`。
     * 为了寻找更短的解，将左边界移除并右移 $l$：`sum -= a[l], l++`。
  4. 重复此过程直至右指针到达边界。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int minSubArrayLen(int t, const vector<int>& a) {
    int n = a.size();
    int minLen = INT_MAX;
    long long sum = 0; // 防止局部溢出
    int l = 0;

for (int r = 0; r < n; ++r) {
        sum += a[r]; // 1. 扩展右边界
        while (sum >= t) { // 2. 窗口达标，收缩左边界
            minLen = min(minLen, r - l + 1);
            sum -= a[l];
            l++;
        }
    }
    return (minLen == INT_MAX) ? 0 : minLen;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> nums = {2, 3, 1, 2, 4, 3};
    int target = 7;
    cout << "Min length: " << minSubArrayLen(target, nums) << "\n"; // 输出 2 (对应子数组 [4, 3])
    return 0;
}
```
* **时空复杂度分析**：每个元素最多被右指针 $r$ 拷入一次，左指针 $l$ 弹出一遍，总复杂度为严格的 **$O(N)$**，空间复杂度为 **$O(1)$**。

---

### 2.2 无重复字符的最长子串
* **题意概括**：
  给定一个字符串 $s$，找出其中不含有重复字符的**最长子串**的长度。

* **滑动窗口机制**：
  使用滑动窗口 $[l, r]$ 记录当前的无重复子串。借助哈希集合（`std::unordered_set`）来高效率检验字符重合状态：
  * **不重复**：若 $s[r]$ 尚未存在于集合，说明窗口有效，直接加入集合，更新最大长度 `maxLen = max(maxLen, r - l + 1)`，继续右移 $r$。
  * **发生重复**：若 $s[r]$ 已经在集合中，说明窗口 $[l, r]$ 产生了冲突。我们必须**连续收缩左边界 $l$** 并从集合中擦除 $s[l]$，直至冲突的字符 $s[r]$ 被完全推出窗口，再将新 $s[r]$ 存入集合。

```cpp
#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

int lengthOfLongestSubstring(string s) {
    int n = s.length();
    if (n == 0) return 0;
    
    unordered_set<char> lookup;
    int maxLen = 0;
    int l = 0;

for (int r = 0; r < n; ++r) {
        // 若当前字符已存在，说明发生冲突，移动左指针收缩窗口
        while (lookup.count(s[r])) {
            lookup.erase(s[l]);
            l++;
        }
        lookup.insert(s[r]);
        maxLen = max(maxLen, r - l + 1); // 维护最大无重复子段长
    }
    return maxLen;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string str = "abcabcbb";
    cout << "Max length: " << lengthOfLongestSubstring(str) << "\n"; // 输出 3 ("abc")
    return 0;
}
```

---

## 三、 对撞指针（左右指针）

对撞指针常作用于具有**单调性**（如已经排序）的线性表上。设置左指针 $l = 0$，右指针 $r = n - 1$，分别由两端向中间逼近。
对撞指针利用单调递增或递减的性质，使决策具有单方向性，以此能够安全地**排除部分多余的解空间**。

### 3.1 盛最多水的容器（一维非排序数组）
这是对撞指针的一个经典例题。它依赖的是几何面积决定的单调单方向性质，而非数组数值的单调性。

* **数学建模**：
  设两板高度分别为 $a[l]$ 与 $a[r]$，水平跨度为 $r - l$。
  则容器容量公式为：
  $$S = \min(a[l], a[r]) \times (r - l)$$
  假设当前状态下 $a[l] < a[r]$。此时限制容器蓄水高度的短板是左侧的 $a[l]$。
  若我们尝试向左收缩右指针（即执行 `r--`），则两板间跨度 $r - l$ 必然会减小，而新高度 $\min(a[l], a[r-1])$ 的上限依然受限于短板 $a[l]$，因此面积必然不会比原来更大。
  所以，**右指针左移对寻找更大容积没有任何贡献，我们可以安全地排除这些解**。
  唯一的生机在于：**向右移动左指针 $l$**，期待遇到一个更长的板 $a[l+1] > a[l]$，以此来抵消跨度缩短带来的损失。
  
* **决策结论**：每次比较，**哪一侧的板短，就移动哪一侧的指针**。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxArea(const vector<int>& a) {
    int l = 0, r = a.size() - 1;
    int ans = 0;
    while (l < r) {
        int h = min(a[l], a[r]);
        ans = max(ans, h * (r - l));
        if (a[l] < a[r]) {
            l++; // 左边短，移动左指针
        } else {
            r--; // 右边短，移动右指针
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> h = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    cout << "Max area: " << maxArea(h) << "\n"; // 输出 49 (对应板 8 和 7)
    return 0;
}
```

---

### 3.2 两数之和 II（有序数组）
* **题意概括**：
  给定一个已按**升序排列**的整数数组 $a$ 和一个目标值 $t$，寻找其中两个数使其和恰好为 $t$。返回其 0-based 下标。

* **对撞指针逻辑**：
  由于数组升序，我们可以通过调整边界来改变两数之和：
  * 若 `sum == t`：找到答案，返回。
  * 若 `sum < t`：当前的和太小，为了让值变大，应右移左指针（`l++`），使 $a[l]$ 的取值单调增加。
  * 若 `sum > t`：当前的和太大，为了让值变小，应左移右指针（`r--`），使 $a[r]$ 的取值单调缩减。

```cpp
#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSum(const vector<int>& a, int t) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == t) {
            return {l, r};
        } else if (sum < t) {
            l++; // 偏小则增大左边界
        } else {
            r--; // 偏大则减小右边界
        }
    }
    return {};
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> arr = {2, 7, 11, 15};
    int target = 9;
    vector<int> res = twoSum(arr, target);
    if (!res.empty()) {
        cout << "Indices: " << res[0] << ", " << res[1] << "\n";
    }
    return 0;
}
```

---

### 3.3 经典拓展：三数之和（3Sum）
* **题意概括**：
  给定一个包含 $n$ 个整数的无序数组 $a$，找出其中所有不重复的三元组 $(a[i], a[j], a[k])$，使得它们的数值和为 0。

* **算法逻辑**：
  1. **排序**：首先对原数组 $a$ 进行升序排序，创造数值单调性。排序耗时 $O(N \log N)$。
  2. **固定一个数**：使用 `for` 循环固定第一个数 $a[i]$。
  3. **双指针降维**：对于选定的 $a[i]$，问题转化为在剩余右半部分区间 $[i+1, n-1]$ 内寻找两个数，使其和恰好为目标值 $-a[i]$。
  4. **对撞指针维护**：令 $l = i + 1, r = n - 1$，执行对撞判断。
  5. **去重避坑**：
     * 第一个数去重：若 $a[i] == a[i-1]$，为防止产生重复三元组，应直接跳过该轮。
     * 双指针去重：当找到合法三元组后，应双向收缩指针，并**跳过所有与当前 $a[l]$ 和 $a[r]$ 相同的重复元素**。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSum(vector<int>& a) {
    vector<vector<int>> ans;
    sort(a.begin(), a.end()); // 1. 排序
    int n = a.size();

for (int i = 0; i < n - 2; ++i) {
        if (i > 0 && a[i] == a[i - 1]) continue; // 2. 第一个元素去重

int target = -a[i];
        int l = i + 1, r = n - 1;

// 3. 对撞查找
        while (l < r) {
            int sum = a[l] + a[r];
            if (sum == target) {
                ans.push_back({a[i], a[l], a[r]});
                // 4. 双指针移动时跳过相同元素以去重
                while (l < r && a[l] == a[l + 1]) l++;
                while (l < r && a[r] == a[r - 1]) r--;
                l++;
                r--;
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = threeSum(nums);
    for (const auto& v : res) {
        cout << v[0] << " " << v[1] << " " << v[2] << "\n";
    }
    return 0;
}
```
* **复杂度分析**：排序耗时 $O(N \log N)$，外层 `for` 循环执行 $O(N)$ 次，内层双指针对撞搜索开销为 $O(N)$。因此总体时间复杂度为 **$O(N^2)$**，空间复杂度取决于排序算法对辅助栈的开销（一般为 $O(\log N)$）。

---

## 四、 双指针算法核心小结

双指针、滑动窗口与对撞指针

双指针（Two Pointers）是一种核心的算法优化思想。它通过在数据结构（尤其是数组、链表和字符串）上设置两个或多个“指针”（通常为代表数组下标的整型变量或迭代器），并根据特定规则相向或同向移动，从而在一次遍历的过程中解决问题。这种方法能将原本可能是平方级别 $O(N^2)$ 的双重循环暴力枚举，优雅地优化到线性级别 $O(N)$。

根据指针的移动方向与速度，双指针算法通常分为以下三大流派： 1. 快慢指针（同向双指针）：两个指针都从起点出发，以不同的步长同向向前移动。常用于检测链表环路、寻找链表中点或删除有序数组中的重复项。 2. 滑动窗口（尺取法）：同向双指针的一种特定策略。两个指针维护一个具有特定属性的“窗口” $[l, r]$，右指针不断向右扩展，左指针在状态不满足约束时向右收缩，用于解决连续子数组或子串的最值、计数等问题。 3. 对撞指针（左右指针）：两个指针分别位于序列的左右两端，向中间相向移动，直至相遇。常用于有序数组的双数之和、回文判定以及容器盛水等问题。

一、快慢指针（Fast & Slow Pointers）

快慢指针通常在一个序列上使用两个速度不同的指针：慢指针 slow（一般每次向前移动 1 步）和快指针 fast（一般每次向前移动 2 步）。利用这种相对速度差，可以高效探测序列中的特定拓扑结构。

1.1 环形链表检测（Floyd 判环算法）

题意概括：给定一个链表的头节点 head，判断链表中是否存在环（即某个节点的 next 指针指向了其前面的历史节点）。
算法对比：
哈希表法：遍历链表并用哈希表（std::unordered_set）存储访问过的节点指针，若遇到已存在的指针则说明有环。时间复杂度 $O(N)$，空间复杂度 $O(N)$。
快慢指针法（Floyd's Cycle-Finding Algorithm）：时间复杂度 $O(N)$，空间复杂度优化至 $O(1)$。
相对速度原理解析：设慢指针 $s$ 每次走 1 步，快指针 $f$ 每次走 2 步。
无环情况：$f$ 必然先到达链表末尾（nullptr），程序结束。
有环情况：当 $s$ 刚进入环内时，设 $f$ 领先 $s$ 的距离为 $k$，环的物理周长为 $L$。在环内运动时，两指针的相对运动速度为： $$\text{相对速度} = v_f - v_s = 2 - 1 = 1 \quad \text{（步/次）}$$ 这意味着每次移动，$f$ 会缩短与 $s$ 之间的距离 1 个单位。因此，移动 $k$ 次后，两指针必然会在环内重合相遇（即 $f == s$），证明有环。

#include <iostream>
using namespace std;

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

// 判断链表是否有环
bool hasCycle(Node *h) {
    if (!h || !h->next) {
        return false; // 空链表或单节点链表不可能有环
    }
    Node *s = h;
    Node *f = h;
    while (f && f->next) {
        s = s->next;       // 慢指针走 1 步
        f = f->next->next; // 快指针走 2 步
        if (s == f) {      // 相遇则证明存在环
            return true;
        }
    }
    return false; // 快指针顺利触底，无环
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // 构造带环链表: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (环入口为 3)
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    Node* n4 = new Node(4);
    Node* n5 = new Node(5);
    n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n5;
    n5->next = n3; // 形成环

    if (hasCycle(n1)) {
        cout << "Cycle detected.\n";
    } else {
        cout << "No cycle.\n";
    }
    return 0;
}

1.2 寻找链表中点

题意概括：给定一个单链表的头节点 head，找到并返回其中间节点。若链表长度为偶数，则返回第二个中间节点。
快慢指针逻辑：快指针 $f$ 和慢指针 $s$ 均初始化为头节点。 $s$ 每次走 1 步，$f$ 每次走 2 步。由于速度是 2 倍关系，当 $f$ 触及末尾时，$s$ 走过的路径长度刚好是 $f$ 的一半，因此 $s$ 所在位置恰好是链表的中间节点。
奇数长度 (1->2->3->4->5)：
- 初始: $s=1, f=1$ $\to$ 运行1: $s=2, f=3$ $\to$ 运行2: $s=3, f=5$（$f->next$ 为空终止），$s=3$ 为中点。
偶数长度 (1->2->3->4->5->6)：
- 初始: $s=1, f=1$ $\to$ 运行1: $s=2, f=3$ $\to$ 运行2: $s=3, f=5$ $\to$ 运行3: $s=4, f=nullptr$（终止），$s=4$ 为第二个中点。

#include <iostream>
using namespace std;

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

// 寻找并返回链表中点
Node* findMid(Node *h) {
    Node *s = h;
    Node *f = h;
    while (f && f->next) {
        s = s->next;
        f = f->next->next;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // 构造链表 1 -> 2 -> 3 -> 4 -> 5
    Node* n1 = new Node(1);
    n1->next = new Node(2);
    n1->next->next = new Node(3);
    n1->next->next->next = new Node(4);
    n1->next->next->next->next = new Node(5);

    Node* mid = findMid(n1);
    if (mid) {
        cout << "Middle node value: " << mid->val << "\n"; // 输出 3
    }
    return 0;
}

二、滑动窗口（Sliding Window）

滑动窗口通过左指针 $l$ 和右指针 $r$ 维护一个动态区间 $[l, r]$。窗口随着指针的右移在序列上滑动，核心在于：“右指针无脑右移扩展，左指针有条件右移收缩”。

2.1 长度最小的子数组

题意概括：给定一个含有 $n$ 个正整数的数组 $a$ 和一个正目标值 $t$。找出数组中满足其区间元素和 $\ge t$ 的长度最小的连续子数组，并返回其长度。若不存在则返回 0。
滑动窗口机制：
初始化 $l = 0, r = 0$，窗口内累加和 sum = 0，最小长度记录为极大值 INT_MAX。
扩展窗口：移动右指针 $r$，累加新数据 sum += a[r]。
收缩窗口：只要当前窗口满足条件（sum >= t），说明找到了一个可行解：
- 尝试更新最小长度：minLen = min(minLen, r - l + 1)。
- 为了寻找更短的解，将左边界移除并右移 $l$：sum -= a[l], l++。
重复此过程直至右指针到达边界。

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

int minSubArrayLen(int t, const vector<int>& a) {
    int n = a.size();
    int minLen = INT_MAX;
    long long sum = 0; // 防止局部溢出
    int l = 0;

    for (int r = 0; r < n; ++r) {
        sum += a[r]; // 1. 扩展右边界
        while (sum >= t) { // 2. 窗口达标，收缩左边界
            minLen = min(minLen, r - l + 1);
            sum -= a[l];
            l++;
        }
    }
    return (minLen == INT_MAX) ? 0 : minLen;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> nums = {2, 3, 1, 2, 4, 3};
    int target = 7;
    cout << "Min length: " << minSubArrayLen(target, nums) << "\n"; // 输出 2 (对应子数组 [4, 3])
    return 0;
}

时空复杂度分析：每个元素最多被右指针 $r$ 拷入一次，左指针 $l$ 弹出一遍，总复杂度为严格的 $O(N)$，空间复杂度为 $O(1)$。

2.2 无重复字符的最长子串

题意概括：给定一个字符串 $s$，找出其中不含有重复字符的最长子串的长度。
滑动窗口机制：使用滑动窗口 $[l, r]$ 记录当前的无重复子串。借助哈希集合（std::unordered_set）来高效率检验字符重合状态：
不重复：若 $s[r]$ 尚未存在于集合，说明窗口有效，直接加入集合，更新最大长度 maxLen = max(maxLen, r - l + 1)，继续右移 $r$。
发生重复：若 $s[r]$ 已经在集合中，说明窗口 $[l, r]$ 产生了冲突。我们必须连续收缩左边界 $l$ 并从集合中擦除 $s[l]$，直至冲突的字符 $s[r]$ 被完全推出窗口，再将新 $s[r]$ 存入集合。

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

int lengthOfLongestSubstring(string s) {
    int n = s.length();
    if (n == 0) return 0;

    unordered_set<char> lookup;
    int maxLen = 0;
    int l = 0;

    for (int r = 0; r < n; ++r) {
        // 若当前字符已存在，说明发生冲突，移动左指针收缩窗口
        while (lookup.count(s[r])) {
            lookup.erase(s[l]);
            l++;
        }
        lookup.insert(s[r]);
        maxLen = max(maxLen, r - l + 1); // 维护最大无重复子段长
    }
    return maxLen;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string str = "abcabcbb";
    cout << "Max length: " << lengthOfLongestSubstring(str) << "\n"; // 输出 3 ("abc")
    return 0;
}

三、对撞指针（左右指针）

对撞指针常作用于具有单调性（如已经排序）的线性表上。设置左指针 $l = 0$，右指针 $r = n - 1$，分别由两端向中间逼近。对撞指针利用单调递增或递减的性质，使决策具有单方向性，以此能够安全地排除部分多余的解空间。

3.1 盛最多水的容器（一维非排序数组）

这是对撞指针的一个经典例题。它依赖的是几何面积决定的单调单方向性质，而非数组数值的单调性。

数学建模：设两板高度分别为 $a[l]$ 与 $a[r]$，水平跨度为 $r - l$。则容器容量公式为： $$S = \min(a[l], a[r]) \times (r - l)$$ 假设当前状态下 $a[l] < a[r]$。此时限制容器蓄水高度的短板是左侧的 $a[l]$。若我们尝试向左收缩右指针（即执行 r--），则两板间跨度 $r - l$ 必然会减小，而新高度 $\min(a[l], a[r-1])$ 的上限依然受限于短板 $a[l]$，因此面积必然不会比原来更大。所以，右指针左移对寻找更大容积没有任何贡献，我们可以安全地排除这些解。唯一的生机在于：向右移动左指针 $l$，期待遇到一个更长的板 $a[l+1] > a[l]$，以此来抵消跨度缩短带来的损失。
决策结论：每次比较，哪一侧的板短，就移动哪一侧的指针。

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

int maxArea(const vector<int>& a) {
    int l = 0, r = a.size() - 1;
    int ans = 0;
    while (l < r) {
        int h = min(a[l], a[r]);
        ans = max(ans, h * (r - l));
        if (a[l] < a[r]) {
            l++; // 左边短，移动左指针
        } else {
            r--; // 右边短，移动右指针
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> h = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    cout << "Max area: " << maxArea(h) << "\n"; // 输出 49 (对应板 8 和 7)
    return 0;
}

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

题意概括：给定一个已按升序排列的整数数组 $a$ 和一个目标值 $t$，寻找其中两个数使其和恰好为 $t$。返回其 0-based 下标。
对撞指针逻辑：由于数组升序，我们可以通过调整边界来改变两数之和：
若 sum == t：找到答案，返回。
若 sum < t：当前的和太小，为了让值变大，应右移左指针（l++），使 $a[l]$ 的取值单调增加。
若 sum > t：当前的和太大，为了让值变小，应左移右指针（r--），使 $a[r]$ 的取值单调缩减。

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

vector<int> twoSum(const vector<int>& a, int t) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == t) {
            return {l, r};
        } else if (sum < t) {
            l++; // 偏小则增大左边界
        } else {
            r--; // 偏大则减小右边界
        }
    }
    return {};
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> arr = {2, 7, 11, 15};
    int target = 9;
    vector<int> res = twoSum(arr, target);
    if (!res.empty()) {
        cout << "Indices: " << res[0] << ", " << res[1] << "\n";
    }
    return 0;
}

3.3 经典拓展：三数之和（3Sum）

题意概括：给定一个包含 $n$ 个整数的无序数组 $a$，找出其中所有不重复的三元组 $(a[i], a[j], a[k])$，使得它们的数值和为 0。
算法逻辑：
排序：首先对原数组 $a$ 进行升序排序，创造数值单调性。排序耗时 $O(N \log N)$。
固定一个数：使用 for 循环固定第一个数 $a[i]$。
双指针降维：对于选定的 $a[i]$，问题转化为在剩余右半部分区间 $[i+1, n-1]$ 内寻找两个数，使其和恰好为目标值 $-a[i]$。
对撞指针维护：令 $l = i + 1, r = n - 1$，执行对撞判断。
去重避坑：
- 第一个数去重：若 $a[i] == a[i-1]$，为防止产生重复三元组，应直接跳过该轮。
- 双指针去重：当找到合法三元组后，应双向收缩指针，并跳过所有与当前 $a[l]$ 和 $a[r]$ 相同的重复元素。

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

vector<vector<int>> threeSum(vector<int>& a) {
    vector<vector<int>> ans;
    sort(a.begin(), a.end()); // 1. 排序
    int n = a.size();

    for (int i = 0; i < n - 2; ++i) {
        if (i > 0 && a[i] == a[i - 1]) continue; // 2. 第一个元素去重

        int target = -a[i];
        int l = i + 1, r = n - 1;

        // 3. 对撞查找
        while (l < r) {
            int sum = a[l] + a[r];
            if (sum == target) {
                ans.push_back({a[i], a[l], a[r]});
                // 4. 双指针移动时跳过相同元素以去重
                while (l < r && a[l] == a[l + 1]) l++;
                while (l < r && a[r] == a[r - 1]) r--;
                l++;
                r--;
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = threeSum(nums);
    for (const auto& v : res) {
        cout << v[0] << " " << v[1] << " " << v[2] << "\n";
    }
    return 0;
}

复杂度分析：排序耗时 $O(N \log N)$，外层 for 循环执行 $O(N)$ 次，内层双指针对撞搜索开销为 $O(N)$。因此总体时间复杂度为 $O(N^2)$，空间复杂度取决于排序算法对辅助栈的开销（一般为 $O(\log N)$）。

四、双指针算法核心小结

双指针流派	指针初始指向	指针移动规则	核心适用场景	经典题型代表
快慢指针	同一起点（通常为头节点）	快慢指针速度呈倍数差同向推进	链表拓扑结构探针、找环路、求中点	链表有环判定、链表求中点
滑动窗口	同一端点（区间起点 $0$）	右边界无脑向右扩展，左边界有条件向右收缩	维护连续区间的最值、计数或频率约束	长度最小子数组、最长无重复子串
对撞指针	两侧端点（$0$ 与 $n-1$）	两个指针向中间相向运动	利用单调性缩减排他性的解空间	两数/三数之和、盛最多水容器

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com