[双指针] 判断子序列(模板题)

文章目录

0. 前言

以前双指针的专栏一直没放啥题目进去，都是作为中间算法的一步，感觉也不经典。这个问题是蛮经典的双指针问题。

1. 双指针

2816. 判断子序列

思路：

• 双指针顺序找就行了，双指针算法能够保证有答案一定会被找出来
• 注意，在此顺序找的是 b 数组第一个与 a 数组当前位置相同的点

代码：

#include <iostream>

using namespace std;

const int N = 1e5+5;

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

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int j = 0; j < m; ++j) cin >> b[j];
    
    int i = 0, j = 0;
    bool sucess = false;
    while (i < n && j < m) {
        if (a[i] == b[j]) ++i;
        ++j;
    }
    puts(i == n ? "Yes" : "No");
    return 0;
}