双指针算法有两类:

  1. 两个指针分别指向不同的序列(归并排序),属于对撞指针
  2. 两个指针指向同一个序列(快排),属于快慢指针

模板

for (int i = 0, j = 0; i < n; i++) {
    while(j < i && check(i, j)) {
    j++;
    }
    // 每道题的具体逻辑
}

特点

所有双指针算法时间复杂度都是$O(n)$,将朴素算法优化到$O(n)$。

例题

1.输出单个字符

给定一行字符串,对字符串进行切分。

输入格式

一行字符串

输出格式

多行字符串

输入样例

aaa bbb ccc

输出样例

aaa
bbb
ccc

【参考程序】

#include <iostream>
#include <string.h>
using namespace std;

int main() {
    char str[1001];
    cin.getline(str,1001);
    int n = strlen(str);
    for (int i = 0; str[i]; i++) {
        int j = i;
        while(j < n && str[j]!= ' ') j++;
  
        // 这道问题的具体逻辑
        for (int k = i ; k < j; k++)
        cout << str[k];
        cout << endl;
        i = j;
    }
    return 0;
}

2.最长连续不重复子序列

给定一个长度为 nn 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。

输入格式

第一行包含整数 n

第二行包含 n 个整数(均在 0~100000 范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围

1≤n≤105

输入样例:

5
1 2 2 3 5

输出样例:

3

【算法分析】

朴素做法:

for (int i = 0; i < n; i++)
    for (int j = 0; j <= i; j++)
        if (check(j, i)) {
        res = max(res,i - j + i);
    }

双指针做法:

for (int i = 0, j = 0; i < n; i++) {
    while(j <= i && check(i,j)) j++;
    res = max(res, i - j + 1);
}

【参考程序】

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

const int N = 100010;

int n;
int a[N];
int s[N];

int main() {
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    int res = 0;

    for (int i = 0, j = 0; i < n; i++) {
        s[a[i]]++;
        while(s[a[i]] > 1) {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res;
    return 0;
}

3.数组元素的目标和

给定两个升序排序的有序数组 A 和 B,以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x 的数对 (i,j)。

数据保证有唯一解。

输入格式

第一行包含三个整数 n,m,x,分别表示 A 的长度,B 的长度以及目标值 x。

第二行包含 n 个整数,表示数组 A。

第三行包含 m 个整数,表示数组 B。

输出格式

共一行,包含两个整数 i 和 j。

数据范围

数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109

输入样例:

4 5 6
1 2 4 7
3 4 6 8 9

输出样例:

1 1

【算法分析】

双指针主要先通过暴力算法中找到单调性,比如这两个数组都是单调递增,我们可以用i指向第一个数组的头,使用j指向第二个数组的尾部,遍历第一个数组时,如果a[i] + b[j] > x,则j只能时递减的,这就构造了一个单调性。

(双指针) O(n)

i0开始 从前往后遍历

jm - 1开始 从后向前遍历

和纯暴力的O(n2) 算法的区别就在于

j指针不会回退

【参考程序】

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

const int N = 100010;

int a[N];
int b[N];
int m, n, x;

int main() {
    scanf("%d %d %d",&n ,&m, &x);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);

    for (int i = 0, j = m - 1; i < n; i++) {
        while(j >= 0 && a[i] + b[j] > x) {
            j--;
        }

        if (a[i] + b[j] == x) {
            printf("%d %d", i, j);
            break;
        }
    }

    return 0;
}

4.判断子序列

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列 而得的序列,例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

输入格式

第一行包含两个整数 n,m。

第二行包含 n 个整数,表示 a1,a2,…,an。

第三行包含 m 个整数,表示 b1,b2,…,bm。

输出格式

如果 a 序列是 b 序列的子序列,输出一行 Yes

否则,输出 No

数据范围

1≤n≤m≤105,
−109≤ai,bi≤109

输入样例:

3 5
1 3 5
1 2 3 4 5

输出样例:

Yes

【参考程序】

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

const int N = 100010;

int n, m, t;
int a[N];
int b[N];

int main() {
    scanf("%d %d",&n, &m);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int j = 0; j < m; j++) scanf("%d", &b[j]);

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] == b[j]) i++;
        j++;
    }

    if (i == n) puts("Yes");
    else puts("No");

    return 0;
}

最后修改:2022 年 01 月 04 日
如果觉得我的文章对你有用,请随意赞赏