双指针

2021-10-26 常用算法 双指针

# 一、算法思想

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

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // ...
    }
}
1
2
3
4
5

常见问题分类:

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

# 二、算法模板

C++

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

# 三、代码实战

# AcWing 0799


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

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

输入格式

第一行包含整数 nn

第二行包含 nn 个整数(均在 01050∼10^5 范围内),表示整数序列。

输出格式

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

数据范围

1n1051 \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;
}
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

# AcWing 0800


题目:数组元素的目标和

给定两个升序排序的有序数组 AABB,以及一个目标值 xx

数组下标从 00 开始。

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

数据保证有唯一解。

输入格式

第一行包含三个整数 n,m,xn,m,x,分别表示 AA 的长度,BB 的长度以及目标值 xx

第二行包含 nn 个整数,表示数组 AA

第三行包含 mm 个整数,表示数组 BB

输出格式

共一行,包含两个整数 iijj

数据范围

  • 数组长度不超过 10510^5
  • 同一数组内元素各不相同
  • 1数组元素1091 \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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# AcWing 2816


题目:判断子序列

给定一个长度为 nn 的整数序列 a1,a2,,ana_1,a_2,\cdots,a_n 以及一个长度为 mm 的整数序列 b1,b2,,bmb_1,b_2,\cdots,b_m

请你判断 aa 序列是否为 bb 序列的子序列。

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

输入格式

第一行包含两个整数 n,mn,m,分别表示 AA 的长度和 BB 的长度。

第二行包含 nn 个整数,表示数组 AA

第三行包含 mm 个整数,表示数组 BB

输出格式

如果 aa 序列是 bb 序列的子序列,输出一行 Yes

否则,输出 No

数据范围

1nm1051 \le n \le m \le 10^5
109ai,bi109−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;
}
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
Last Updated: 2023-01-28 4:31:25