双指针算法 复习

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

#include <iostream>

using namespace std;
const int N = 100010;

int q[N], s[N];

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> q[i];

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

    cout << res << endl;

    return 0;
}

AcWing 800.数组元素的目标和

#include <iostream>

using namespace std;
const int N = 100010;

int a[N], b[N];

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    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;
    }

    return 0;
}

AcWing 2816.判断子序列

#include <iostream>

using namespace std;
const int N = 100010;

int a[N], b[N];

int main()
{
    int n, m;
    cin >> n >> m;

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

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

    (i == n) ? puts("Yes") : puts("No");

    return 0;
}