AcWing 2816. 判断子序列（双指针算法）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 2816. 判断子序列（双指针算法）原题链接简单

作者：

林小鹿 , 2020-11-19 19:36:51 , 所有人可见 , 阅读 17666

251

101

双指针算法

1.j指针用来扫描整个b数组，i指针用来扫描a数组。若发现a[i] == b[j]，则让i指针后移一位。
2.整个过程中，j指针不断后移，而i指针只有当匹配成功时才后移一位，若最后若i == n，则说明匹配成功。

为什么双指针做法是正确的？

整个过程中j指针不断扫描b数组并且向后移动，相当于不断给i指针所指向的a数组创建匹配的机会，只有匹配成功时i指针才会向后移动一位，当i == n时，说明全部匹配成功。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n; i++) scanf("%d",&a[i]);
    for(int j = 0;j < m; j++) scanf("%d",&b[j]);

    int i = 0;
    for(int j = 0;j < m; j++)
    {
        if(i < n&&a[i] == b[j])  i++;
    }
    if(i == n) puts("Yes");
    else puts("No");
    return 0;
}

78 评论

小半 2023-02-10 20:19

#简洁还好理解，大佬的思维就是厉害！

Syihang 2023-03-22 23:31

一个月前就做到这了，大佬厉害

小半 2023-03-23 13:03 回复了 Syihang 的评论

我现在都卡在数论了555

百无禁忌_5 2022-05-13 07:52

怎么样才能向大佬一样写这么通俗易懂的题解呀

云之端i 2023-10-18 20:14

只要能够按顺序匹配到，字符串前边的匹配任务就完成了

东游特等兵 1个月前

大佬牛逼我思路差不多但就是写不出来这么简洁的

金城武 2023-12-20 23:13

大佬nb

日驭 2023-12-14 18:21

牛啊牛啊

Far1 2023-05-09 19:00

写的真的太厉害了

acwing_ap_f 1个月前

一下子就看懂了，谢谢大佬

二马山石 3个月前

#include<iostream>
using namespace std;
const int N =100010;
int q[100010],s[100010];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>q[i];
    for(int j=0;j<m;j++)cin>>s[j];
    int l=0;
    int num=0;
    for(int j=0;j<n;j++)
    {
        while(l<m)
        {
            if(s[l]==q[j])
            {
                num++;
                l++;
                break;
            }
            l++;
        }
    }
    if(num==n)cout<<"Yes";
    elsecout<<"No";
    return 0;
}
大佬们我这样写是不太好吗？

汪超 8个月前

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], b[N];

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for (int j = 1; j <= m; j ++) scanf("%d", &b[j]);

    int j = 1, i = 1;
    for (; j <= m; j ++) if (a[i] == b[j]) i ++;

    if (i > n) printf("Yes");
    else printf("No");

    return 0;
}

杉夜 8个月前

if(i < n&&a[i] == b[j]) i; 改成 while(i < n&&a[i] == b[j]) i; 答案会不一样有大佬能指点一下吗

..._37 8个月前

用while的话i执行完，会再次进入while循环进行判断，而不是执行j

linkingcoder 2023-10-12 17:33

大佬啊

acwing_71000 2023-09-05 19:55

太优雅了

walili 2023-02-28 09:49

#include [HTML_REMOVED]

using namespace std;

#define int long long
#define endl ‘\n’

const int inf = 0x3f3f3f3f;
const int N=1e5+10;
int a[N],b[N],n,m,flag;

void oper()
{
cin>>n>>m;
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;
for(i=1;i<=n;i++)
{
    flag=0;
    for(;j<=m;j++)
    {
        if(a[i]==b[j])
        {
            flag=1;
            j++;
            break;
        }
    }
    if(flag)continue;
    else break;
}
if(i-1==n)
{
    cout<<"Yes"<<endl;
    return ;
}
cout<<"No"<<endl;

}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1; //cin >> t;
while(t–)
oper();

return 0;

}
我的代码是相当丑陋了

xmcti 2023-02-12 22:50

大佬牛逼！！！

苏格拉底不会写诗 2023-01-27 20:43

大佬真的好简洁，羡慕tql
我从i开始的qwq，不过算了下时间复杂度也是O(m+n)，中间加了点条件提前结束，判断一下后面长度够不够

// 双指针 --- 规范模板,简洁代码，时间复杂度O(m+n)

// 双指针---模板不是很规范，自己写的，但时间复杂度算的还是O(N+M)
#include <iostream>
#define N 100010
using namespace std;

int n, m;
long long int a[N], b[N];

int matching(int n, int m){
    int i = 0, j = 0; // 这里的i,j的定义与初始化放在循环外面，保证他的作用域，因为双指针算法的指针是单调的。
    for(; i < n; i++){
        for(; j < m ; j++){
            // 终止条件，匹配失败，而且b序列后续未遍历的元素小于a后续未遍历的元素，则a必然不是b的子序列
            if(b[j] != a[i] && j >= m - n + 1 + i) {
                //cout << "1" << endl; --- 检测
                return 0;
            }
            // 匹配成功条件，a最后一个元素匹配成功
            if(b[j] == a[i] && i == n-1){
                //cout << "2" << endl;--- 检测
                return 1;
            }
            // a序列当前元素匹配成功，但不是最后一个，因此只是推出j的循环，i和j往后移动一位，开始后续遍历
            if(b[j]== a[i]) {
                //cout << "3" << endl;--- 检测
                j++;
                break;
            }
            // 匹配失败，j继续往后遍历匹配
            //cout << "4" << endl;--- 检测
        }
    }
}
int main(){
    cin >> n >> m;
    if(n > m) cout << "Yes";
    for(int i  = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    int x = matching(n, m);
    x == 1? cout << "Yes" : cout << "No";
    return 0;
}