C++ 算法技巧 — 双指针 (Two Pointers)

章节概述

双指针（又称尺取法）通过两个指针在数组上协同移动，将 O(n^2) 暴力优化为 O(n)，
常用于有序数组的查找、区间统计等问题。

核心原理

1. 数学基础

双指针的核心是利用单调性避免重复遍历。每个指针最多移动 n 次，总复杂度 O(n)。

2. 三种模式

模式	指针方向	典型问题
对撞双指针 (左右)	l→ ←r	有序数组两数之和
同向双指针 (快慢)	slow→ fast→	去重、删除元素
滑动窗口 (同向)	l→ r→	最短/最长满足条件的区间

3. 对撞双指针

l = 0, r = n-1
while (l < r):
 sum = a[l] + a[r]
 if sum == target: 找到
 if sum < target: l++ // 和太小，增大
 else: r-- // 和太大，减小

4. 同向双指针 (快慢)

slow = 0
for fast in 1..n-1:
 if a[fast] != a[slow]:
 slow++
 a[slow] = a[fast]
return slow + 1 // 去重后长度

关键数据结构

F_链表_LinkedList — 快慢指针判环、找中点
E_容器_Container — vector 上的双指针操作

同向双指针（快慢指针）

两个指针同向移动，常用于去重、删除元素、链表操作等。

// 示例：移除有序数组中重复元素，返回新长度
int removeDuplicates(int a[], int n) {
 int slow = 0;
 for (int fast = 1; fast < n; fast++)
 if (a[fast] != a[slow])
 a[++slow] = a[fast];
 return slow + 1;
}

对撞双指针

两个指针从两端向中间移动，常用于有序数组中查找两数之和。

// 示例：在有序数组中找两数之和等于 target
bool twoSum(int a[], int n, int target) {
 int l = 0, r = n - 1;
 while (l < r) {
 int sum = a[l] + a[r];
 if (sum == target) return true;
 if (sum < target) l++;
 else r--;
 }
 return false;
}

P1102 A-B 数对

题目: 给出 N 个正整数和一个数 C，求满足 A - B = C 的数对 (A,B) 个数。

思路: 排序后用对撞双指针或二分。转化为 B = A - C，对每个 A 统计 B 的出现次数。

#include <iostream>
#include <algorithm>
using namespace std;
int a[200005];
 
int main() {
 int n, c;
 long long ans = 0;
 cin >> n >> c;
 for (int i = 0; i < n; i++) cin >> a[i];
 sort(a, a + n);
 for (int i = 0; i < n; i++) {
 int target = a[i] - c;
 ans += upper_bound(a, a + n, target) - lower_bound(a, a + n, target);
 }
 cout << ans << endl;
 return 0;
}

P1147 连续自然数和

题目: 把一个自然数 M 表示为连续的若干自然数之和，输出所有方案。

思路: 右指针 r 向右移动，维护区间 [l, r] 的和。若和大于 M 则移动左指针 l；等于 M 则记录答案。

#include <iostream>
using namespace std;
 
int main() {
 int M;
 cin >> M;
 int l = 1, r = 1, sum = 1;
 while (l <= r && r <= M / 2 + 1) {
 if (sum == M) {
 cout << l << " " << r << endl;
 sum -= l++;
 } else if (sum < M) {
 sum += ++r;
 } else {
 sum -= l++;
 }
 }
 return 0;
}

P1638 逛画展

题目: 博览会有 n 幅画排成一行，共有 m 位画家。求一个最短的连续区间，使得该区间内包含所有 m 位画家的作品。

思路: 滑动窗口（同向双指针）。右指针扩展，统计区间内画家数量；当包含全部画家时，收缩左指针。

#include <iostream>
using namespace std;
int a[1000005], cnt[2005];
 
int main() {
 int n, m, kinds = 0;
 cin >> n >> m;
 for (int i = 1; i <= n; i++) cin >> a[i];
 int l = 1, minLen = n + 1, ansL = 1, ansR = n;
 for (int r = 1; r <= n; r++) {
 if (cnt[a[r]] == 0) kinds++;
 cnt[a[r]]++;
 while (kinds == m && l <= r) {
 int len = r - l + 1;
 if (len < minLen) {
 minLen = len;
 ansL = l;
 ansR = r;
 }
 cnt[a[l]]--;
 if (cnt[a[l]] == 0) kinds--;
 l++;
 }
 }
 cout << ansL << " " << ansR << endl;
 return 0;
}

RootStack

探索

C++ 算法技巧 — 双指针 (Two Pointers)

章节概述

核心原理

关键数据结构

同向双指针（快慢指针）

对撞双指针

P1102 A-B 数对

P1147 连续自然数和

P1638 逛画展

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接