AcWing 2816. 判断子序列

文章目录

AcWing 2816. 判断子序列
我的思路
- CODE
欣赏大神代码
给点思考

AcWing 2816. 判断子序列

题目链接：https://www.acwing.com/activity/content/problem/content/2981/

我的思路

直接硬套模版，把两个指针两层循环写上
如果匹配，记录数组更新
遍历记录数组，如果有未标记的值，说明非子串

CODE

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m;
const int N = 1e5 + 10;
int a[N], b[N], cnt[N];

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

    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 = 0; i < n; ++i){
        while(j < m && a[i] != b[j]){
            j++;
        }
        
        if(j < m && a[i] == b[j]){		// 这个判断中 j < m 非常必要
            cnt[i]++;
            j++;
        }
    }
    
    for(int i = 0; i < n; ++i){
        if(cnt[i] == 0){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
}

j < m在 $i f$ 判断中不可缺少，当我们走到b[]最后一位没有匹配成功时，j会自加到j == m，那么b[j] == 0，是数组越界后的第一位'\0'，如果a[i] == 0那么就会匹配成功，尤其是在最后一位时

欣赏大神代码

#include <iostream>
#include <cstring>

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) puts("Yes");
    else puts("No");

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/589289/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。