双指针算法

发表于 更新于 分类于 本文字数： 526 阅读时长 ≈ 2 分钟

双指针核心要义是将含两层嵌套的朴素算法, 利用某种性质(例如单调性)将其优化成O(n)的过程. 有种并发的感觉——一步能干两个人的事情, 就不要等另一个人干完再去做.

双指针一般会结合其他数据结构或者算法一起使用.

通用模板

1
2
3
4
5
6
7
for (int i = 0, j = 0; i < n; i++)
{
    // 也可能是 j = n, 那么条件改为 j > i, 以及 j--
    while (j < i && check(i, j))
        j++;
    // 每道题目的具体逻辑
}

双指针应用

字符串删减

https://www.acwing.com/problem/content/3771/

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
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    int cnt = 0;
    // Brute Force
    // for (int i = 2; i < n; i++)
    // {
    //     if (s[i - 2] == 'x' && s[i - 1] == 'x' && s[i - 2] == 'x')
    //         cnt++;
    // }
    // Optimization
    for (int i = 0, j = 0; i < n; i++)
    {
        if (s[i] == 'x')
        {
            j = i + 1;
            while (j < n && s[j] == 'x')
                j++;
            cnt += max(j - i - 2, 0);
            i = j - 1;
        }
    }
    cout << cnt << endl;
    return 0;
}

最长连续不重复子序列

AcWing 799. 最长连续不重复子序列

朴素算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < n; i++)
    for (int j = 0; j <= i; j++)
        if (check(v1, j, i))
            res = max(res, i - j + 1);
// 检查 [l, r] 区间上有无重复元素
bool check(vector<int>& v1, int l, int r)
{
    for (int i = l + 1; i <= r; i++)
        for (int j = l; j < i; j++)
            if (v1[i] == v1[j])
                return true;
    return false;
}

换用双指针(有点hashmap的感觉):

1
2
3
4
5
6
7
for (int i = 0, j = 0; i < n; i++)
{
    s[a[i]]++;          // a[i]出现的次数(标记)加一
    while (j < i && s[a[i]] > 1)
        s[a[j++]]--;    // 如果存在重复元素 标记减一 j 右移 
    res = max(res, i - j + 1);
}

数组元素的目标和

AcWing 800. 数组元素的目标和

朴素做法:

1
2
3
4
5
6
7
8
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < m; j++)
    {
        if(A[i] + B[j] == x)
            cout << i << ' ' << j << endl;
    }
}

双指针:

1
2
3
4
5
6
7
for(int i = 0, j = m - 1; i < n; i++)
{
    while (j >= 0 && A[i] + B[j] > x)
        j--;
    if(j >= 0 && A[i] + B[j] == x)
        cout << i << ' ' << j << endl;
}

判断子序列

AcWing 2816. 判断子序列

1
2
3
4
5
6
7
int i, j;
for(i = 0, j = 0; j < m; j++)
{
    if(i < n && a[i] == b[j])
        i++;
}
printf("%s\n", (i == n) ? "Yes" : "No");