[AcWing]2816. 判断子序列（C++实现）

[AcWing]2816. 判断子序列（C++实现）

[AcWing]2816. 判断子序列（C++实现）

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

思路： 双指针,i 指向a数组，j 指向b数组，当a[i] == b[j]时，i，j同时后移，当结束时判断i是否遍历完，是则返回true，证明a是b的子数组，否之不是。

注意：本题不要求子序列是连续的

3. 解法

---------------------------------------------------解法：双指针---------------------------------------------------

#include
using namespace std;

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

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]);
    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;
}

4. 可能有帮助的前置习题

• [AcWing]799. 最长连续不重复子序列（C++实现）双指针模板题

5. 所用到的数据结构与算法思想 6. 总结

双指针的应用