首页 程序设计 基础算法 双指针

# 题目大意

给定一个长度为 nn 的整数序列 a1,a2,...,ana_1, a_2, ..., a_n 以及一个长度为 mm 的正数序列 b1,b2,...,bmb_1, b_2, ..., b_m
请你判断 aa 序列是否为 bb 序列的子序列

子序列指序列的一部分按原有次序排列而得到的序列（可以不连续）

# 数据范围

  • 1≤n≤m≤1051 \le n \le m \le 10^5

# 题解

扫一遍，看能不能扫完 aa 数据即可

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve () {
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
        
    for (int i = 1, j = 1; i <= n; i++) {
        while (j <= m && a[i] != b[j])
            j++;
        
        if ((j <= m && a[i] != b[j]) || j > m) {
            cout << "No" << endl;
            return;
        }
        
        j++;
    }
    
    cout << "Yes" << endl;
}

还有个更简单的写法
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve () {
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
        
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (a[i] == b[j])
            i++;
        j++;
    }
    
    cout << (i == n + 1 ? "Yes" : "No") << endl;
}