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   // 去重后长度

关键数据结构

D_链表_LinkedList — 快慢指针判环、找中点
A_容器_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 逛画展

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接