#双指针

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

#问题背景

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

例如，对下面的输入数据

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

这里的 6 个数字中，一共有三对满足条件。

• 1+8=9
• 2+7=9
• 3+6=9

因此输出结果为 3。

#朴素解法

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

参考代码如下：

#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，直到两个指针相遇停止移动，计算结束。

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

参考代码如下：

#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。

如输入数据：

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

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

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

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

参考代码如下：

#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. 环形检测：链表是否有环、环的入口等

#总结

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