AcWing 2816. 判断子序列

AcWing 2816. 判断子序列 - 糖豆爸爸 - 博客园

AcWing 2816. 判断子序列 [简单]

1 题目描述

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

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

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

输入格式
第一行包含两个整数 n,m。

第二行包含 n 个整数，表示 a1,a2,…,an。

第三行包含 m 个整数，表示 b1,b2,…,bm。

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

否则，输出 No。

数据范围
1 ≤ n ≤ m ≤ 10^5^,
−10^9^ ≤ ai, bi ≤ 10^9^

输入样例：

3 5
1 3 5
1 2 3 4 5

输出样例：

Yes

2 WA代码

emmm, 暴力? 但这也不对啊. 想不出来…

通过了 7/17 个数据.

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m, flag = 0;
int a[N], b[N], s[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    int k = n - 1;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int j = 0; j < m; j ++ ) cin >> b[j];
    
    for (int i = n - 1, j = m - 1; ~i; i -- ) {
        if (a[i] > b[j]) {
            flag = 1;
            break;
        }
        
        while (j > 0 && a[i] < b[j]) j -- ;
        
        if (a[i] == b[j]) {
            s[k -- ] = a[i];
        }
    }
    
    for (int i = 0; i < n; i ++ ){
        if (a[i] != s[i])
            flag = 1;
    }
    if (!flag) puts("Yes");
        else puts("No");
    
    return 0;
}

3 解题思路

程序框架:

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) cin >> b[i];

    /* 关键代码 */

    return 0;
}

3.1 双指针遍历 + 外层循环判断

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");

其中内层循环判断可以优化, 在外层循环中增加了一个判断条件来提前退出循环，以减少不必要的比较操作。

// 如果 b 序列剩余的元素数量 < a 序列剩余的元素数量, 那么肯定不满足子序列的要求
while (i < n && m - j + 1 >= n - i + 1)

3.2 双指针 + 内层循环过滤 (模板) * 2

  • 1. 在序列 b 中查找与 a[i] 相等的元素。

    在这种方法中，i 主要用于遍历序列 a，而 j 则用于在序列 b 中查找与 a[i] 相等的元素。

    • 每当遍历到 a 中的一个元素 a[i] 时，就在序列 b 中从当前位置 j 开始向后查找是否有与 a[i] 相等的元素。
    • 如果找到了，则 j 移动到该元素的位置，然后 i 和 j 同时向后移动一位。
    • 如果没有找到与 a[i] 相等的元素，那么 a 序列就不是 b 序列的子序列，直接输出 "No" 并结束程序。
for (int i = 0, j = 0; i < n; i ++ ) {
    while (j < m && a[i] != b[j]) j ++ ;    // 在 b 中找 a[i]
    
    if (j == m) {       // b 已经扫描完, 没有找到子序列 a
        puts("No");
        return 0;
    }
    j ++ ;      // j 后移一位才能与 i ++ 匹配
}

puts("Yes");    // 当 i == n 跳出循环, 找到子序列 a

  • 2. 引入额外变量 t，表示序列 a 中还没有被匹配的元素数量。

    在循环中，每当找到与 a[i] 相等的元素时，就将 t-- ，表示找到了一个匹配的元素。循环结束后，如果 t 大于 0，那么说明序列 a 中还有元素没有被匹配到，此时输出 "No"；否则输出 "Yes"。

    这种方法思路清晰简洁，通过 t 来记录未匹配的元素数量，不需要额外的条件判断，直接通过 t 的值来判断是否为子序列。

int t = n;      // t 是 a 数组还没有被匹配的数量
for (int i = 0, j = 0; i < n; i ++ ) {
    while (j < m && a[i] != b[j]) j ++ ;    // while 进行过滤
    
    if (j >= m) break;      // 过滤时发现 j 已经到头了, break
    
    // 匹配状态, 其实暗藏着一个 if 条件 a[i] == b[j], 这就是操作的条件
    t -- ;
    j ++ ;      // 匹配到了就下一个
}
// 数量为 0 则匹配成功, 否则说明 b 数组按照 a 数组匹配还没有匹配完 a 数组就没了, 那么结束
if (t > 0) puts("No");
else puts("Yes");

3.3 双指针 + 单层循环

循环中 j 作为快指针，遍历序列 b，而 i 作为慢指针，用来遍历序列 a。

  1. j 指针用来扫描整个 b 数组，i 指针用来扫描 a 数组。若发现 a[i] == b[j]，则让 i 指针后移一位
  2. 整个过程中，j 指针不断后移，而 i 指针只有当匹配成功时才后移一位，若最后 i == n , 则说明匹配成功
int i = 0;      // i 放外面, 之后会用到它判断是否走到了最后
                // 单层循环, 谁长循环谁, 长的跑快指针
for (int j = 0; j < m; j ++ )
    // 短的跑慢指针, (1)注意控制指针不越界; (2)满足条件时慢指针 i ++
    if (i < n && a[i] == b[j]) i ++ ;

if (i == n) puts("Yes");
else puts("No");