双指针算法总结-526互联

双指针算法分为两类：第一类指向一个序列（更多的情况），第二类指向两个序列。

基本的代码框架是：

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

核心思想：运用单调性等性质，将O(n²)的算法优化到O(n)。

种类：快排的划分、归并排序的归并、KMP算法等。

第一类：指向一个序列

题目链接：

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

题解：

遍历区间，对于每一个i，找到最左边的j，使得[j, i]区间中的数不包含重复元素。满足单调性，可以使用双指针算法。

代码：

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], 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 << endl;
    
    return 0;
}

第二类：指向两个序列

题目链接：

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

题解：

对于有序数组中的每一个数A[i]，在B数组中找到最左边的数B[j]，使得A[i] + B[j] >= x。基于这一思想，i从1到n遍历，j从m - 1到0遍历，利用单调性，使用双指针算法，找到第一个满足条件A[i] + B[j] == x的数对即可。

代码：

#include <iostream>

using namespace std;

const int N = 100010;

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

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\n", i, j);
            break;
        }
    }
    
    return 0;
}

补充题目链接：

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

题解：

从左到右遍历a序列，从b序列中找到与a序列相等的数字，找到所有a序列的匹配，则可以输出Yes，否则输出No。

代码：

#include <iostream>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);
    
    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;
}