双指针

一、算法思想

双指针算法的核心思想，是将如下 $O(n^2)$ 的朴素解法优化到 $O(n)$。

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // ...
    }
}

常见问题分类：

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

二、算法模板

C++

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

三、代码实战

AcWing 0799

---

题目：最长连续不重复子序列

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

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数（均在 $0∼10^5$ 范围内），表示整数序列。

输出格式

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

数据范围

$1 \le n \le 10^5$

输入样例：

5

1 2 2 3 5

输出样例：

3

解答代码：

#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 ans = 0;
    for (int i = 0, j = 0; i < n; i++) {
        s[a[i]]++;
        while (s[a[i]] > 1) {
            s[a[j]]--;
            j++;
        }
        ans = max(ans, i - j + 1);
    }
    
    cout << ans << endl;
    
    return 0;
}

AcWing 0800

---

题目：数组元素的目标和

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

数组下标从 $0$ 开始。

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

数据保证有唯一解。

输入格式

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

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

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

输出格式

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

数据范围

• 数组长度不超过 $10^5$
• 同一数组内元素各不相同
• $1 \le 数组元素 \le 10^9$

输入样例：

4 5 6

1 2 4 7

3 4 6 8 9

输出样例：

1 1

解答代码：

#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);
        }
    }
    return 0;
}

AcWing 2816

---

题目：判断子序列

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$ 以及一个长度为 $m$ 的整数序列 $b_1,b_2,\cdots,b_m$。

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

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 $\{a_1,a_3,a_5\}$ 是序列 $\{a_1,a_2,a_3,a_4,a_5\}$ 的一个子序列。

输入格式

第一行包含两个整数 $n,m$，分别表示 $A$ 的长度和 $B$ 的长度。

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

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

输出格式

如果 $a$ 序列是 $b$ 序列的子序列，输出一行 Yes。

否则，输出 No。

数据范围

$1 \le n \le m \le 10^5$

$−10^9 \le a_i,b_i \le 10^9$

输入样例：

3 5

1 3 5

1 2 3 4 5

输出样例：

Yes

解答代码：

#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) printf("Yes");
    else printf("No");
    
    return 0;
}