---
title: "双指针"
description: "前缀和、差分、双指针、滑动窗口等高频算法套路。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 双指针

![](https://img.dailyup.xyz/originals/8208462637304-4bc22e41-7e46-4bba-98f6-133a0983d86c.png)


**双指针（Two Pointers）是一种通过使用两个指针（索引）协同遍历数据结构的算法技巧**。这两个指针可以同向移动，也可以相向移动，根据问题需求采取不同的移动策略。

## 问题背景

给定一组共 `n` 个整数，需要计算这 `n` 个整数中满足两数之和为 `target` 的数对共有多少对？

例如，对下面的输入数据

```
6 9
1 2 3 6 7 8
```

第一行包括两个数字，第一个 n 为 6，表示接下来要输入 6 个整数（第二行中的 6 个数），第一行中的第二个数字 `target` 为 9，表示要求输入的 6 个整数中，有多少对数字之和刚好为 9。

这里的 6 个数字中，一共有三对满足条件。
- `1+8=9`
- `2+7=9`
- `3+6=9`

因此输出结果为 3。

## 朴素解法

容易想到，可以用枚举法去实现，从左至右，依次选择一个数字，然后与后面其它的数字挨着去相加，看结果是否满足要求，满足计数器加 1，直到全部枚举完成。

参考代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, target, cnt;
int q[110];

int main() {
  cin >> n >> target;
  
  for (int i = 0; i < n; i++) cin >> q[i];
  // 枚举法依次两两求和
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (q[i] + q[j] == target) {
        cnt++;
      }
    }
  }
  
  cout << cnt << endl;
  return 0;
}
```

这里朴素解法的时间复杂度是 $O(n^2)$。

## 双指针求解

双指针正好适合解决上面这类问题，我们可以设定一前一后两个指针，分别从首尾出发，向中间移动，每移动一次，计算当前这两个指针的数字之和，看是否满足要求，满足则计数器加 1，直到两个指针相遇停止移动，计算结束。

需要注意的是，在使用双指针来计算数字之和时，需要先对数组进行排序。

参考代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, target, cnt;
int q[110];

int main() {
  cin >> n >> target;
  
  for (int i = 0; i < n; i++) cin >> q[i];
  
  // 设定首尾指针的初始位置
  int left = 0, right = n - 1;
  
  while (left < right) {
    int sum = q[left] + q[right];
    if (sum == target) {
      cnt++;
      left++;
      right--;
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  
  cout << cnt << endl;
  return 0;
}
```

使用双指针求解上面的问题，效率更高了，时间复杂度从 $O(n^2)$ 降到了 $O(n)$。

## 拓展-快慢指针

快慢指针是双指针技术的一种特殊形式，它**使用两个指针以不同的速度遍历数据结构（通常是数组或链表）**。快指针移动速度是慢指针的两倍（或其它倍数关系），通过这种速度差来解决特定问题。

### 移除数组特定元素

对于一组给定的 `n` 个整数，移除当中指定的元素 `k`。

如输入数据：

```
6 3
3 2 2 3 4 5
```

第一行两个整数，第一个为 `n`，表示要输入 6 个整数，第二个为 `k`，表示要移除这 6 个整数中的数字 3。

移除后，其它整数保持原顺序不变输出，这里应该输出：

```
2 2 4 5
```

当然，这里的题目比较简单，我们可以使用循环，直接去对比，把所有不是 `k` 的整数输出即可，但如果我们还需要对移除后的数据再统一做其它处理呢，我们通常就需要一个额外的数组，用来存储所有非 `k` 的整数。

如果使用快慢指针，我们可以直接对原数组操作，不需要额外空间。

参考代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, k, q[110];

int main() {
  cin >> n >> k;
  
  for (int i = 0; i < n; i++) cin >> q[i];
  
  // 慢指针指向新数组的下一个位置
  int slow = 0; 
  // 快指针遍历数组
  for (int fast = 0; fast < n; fast++) { 
    if (q[fast] != k) {
      q[slow++] = q[fast]; // 只保持不等 k 的元素
    }
  }
  
  for (int i = 0; i < slow; i++) {
    cout << q[i] << " ";
  }
  
  return 0;
}
```

可以看到，之所以快指针叫“快”，它移动的速度会比慢指针更快，**`fast` 指针更新 1 次或多次，`slow` 指针才会更新一次**。

## 双指针的优缺点

### 优点

- 显著减少时间复杂度（常从 $O(n^2)$ 降到 $O(n)$）
- 空间复杂度通常为 $O(1)$，不需要额外空间
- 代码实现通常简洁直观

### 缺点

- 通常要求数据预先排序（对撞指针）
- 不适用于所有问题，需要分析问题特性
- 指针移动逻辑有时容易出错

## 双指针的应用

1. **数组/链表操作**：移除元素、合并数组、反转链表等
2. **求和问题**：两数之和、三数之和等
3. **环形检测**：链表是否有环、环的入口等

## 总结

与前缀和类似，双指针技巧看似简单，但能解决许多经典算法问题。理解其核心思想后，可以灵活应用到各种变体问题中。

Source: https://cppguide.xyz/algopatterns/twopointers/index.mdx