双指针算法

1.算法模板

1
2
3
4
for (int i = 0, j = 0; i < n; i ++ ) {
    while (j < i && check(i, j)) j ++;
    /*具体问题逻辑*/
}

常见双指针问题：

  • 对于一个序列，用两个指针维护一段区间
  • 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

2.双指针练习

（1）AcWIng799.最长连续不重复子序列

方法1：暴力法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;

const int MAX = 100010;

int n;
int a[MAX], mark[MAX];

bool check(int low, int high) {
    for (int i = low + 1; i <= high; ++i) {
        for (int j = low; j < i; ++j) {
            if (a[i] == a[j]) return false;
        }
    }
    return true;
}

int main() {
    int res = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (check(j, i)) res = max(res, i - j + 1);
        }
    }
    cout << res << endl;
    return 0;
}
方法2：双指针法

仔细考虑暴力法就会发现，暴力法在解题时有很多地方是重复计算了：

  • 比如 j = 0，i = 5，此时发现 i，j 是满足题解条件的；那么后面的 j = 1到5，i = 5 就不用计算了，肯定是满足条件的。
  • 所以引出了双指针法：既然发现 j = 0，i = 5满足题解条件，那就不用计算 j = 1到5，i = 5了，直接计算 j = 1，i = 6，如果不满足条件，那就计算 j = 2，i = 6，然后接着计算。
  • 这样就是 i 和 j 指针都是从前移到后，也就是计算2n次。时间复杂度是O(2n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;

const int MAX = 100010;

int n;
int a[MAX], mark[MAX];

bool check(int low, int high) {
    for (int i = low + 1; i <= high; ++i) {
        for (int j = low; j < i && mark[a[i]] > 0; ++j) {
            if (a[i] == a[j]) return false;
        }
    }
    return true;
}

int main() {
    int res = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) {
        while (j <= i) {
            if (!check(j, i)) j++;
            else {
                res = max(res, i - j + 1);
                break;
            }
        }
    }
    cout << res << endl;
    return 0;
}
方法3：双指针法（check函数优化）

由于check函数写的不好循环太多，直接是暴力计算找重复数字的，显然不好。

所以引出一个新的check方法：对于寻找是否有重复数字，一般用hash，没人用暴力。

  1. 遍历数组中的每一个元素, 对于每一个i找到j使得[j, i]维护的是以a[i]结尾的最长连续不重复子序列，长度为i-j+1, 将最大的长度res更新。
  2. 对于每一个i如何确定j的位置：由于[j, i - 1]是前一步得到的最长连续不重复子序列，所以如果[j, i]中有重复元素，一定是a[i]重复，因此右移j直到a[i]不重复为止（由于[j, i - 1]已经是前一步的最优解，此时j只可能右移以剔除重复元素a[i]，不可能左移增加元素，因此，j具有单调性、本题可用双指针降低复杂度）。
  3. 用数组count记录子序列a[j ~ i]中各元素出现次数，遍历过程中对于每一个i有四步操作：读入元素a[i] -> 将a[i]出现次数count[a[i]]加1 -> 若a[i]重复则右移j（count[a[j]]要减1） -> 确定j及更新当前长度i - j + 1给res。

image-20230321170323738

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;

const int MAX = 100010;

int n;
int a[MAX], count[MAX];

int main() {
    int res = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0, j = 0; i < n; ++i) {
        count[a[i]]++;
        while (count[a[i]] > 1) {//某个数字的数量大于1该数字重复, 将j指针移动到与i指针相同的位置
            count[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}

参考：https://www.acwing.com/solution/content/23474/

（2）AcWing800.数组元素的目标和

双指针算法就是对暴力法进行优化，如果有单调性，则可以利用单调性将时间复杂度降低一位：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;

const int MAX = 100010;

int n, m, x;
int A[MAX], B[MAX];

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) {
        //int j = m - 1;不可写在for循环中
        while (A[i] + B[j] > x && j >= 0) j--;
        if (A[i] + B[j] == x) {
            printf("%d %d\n", i, j);
            break;
        }
    }
    return 0;
}

（3）AcWing2816.判断子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;

const int N = 100010;

int n, m;
int arr1[N], arr2[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &arr1[i]);
    for (int i = 0; i < m; ++i) scanf("%d", &arr2[i]);
    
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (arr1[i] == arr2[j]) i++;
        j++;
    }
    if (i == n) puts("Yes");
    else puts("No");
    return 0;
}