【双指针5】判断子序列
题解
题目描述
给定两个整数序列 a=a1,a2,…,an 和 b=b1,b2,…,bm,判断序列 a 是否是序列 b 的子序列。
子序列的定义:一个序列通过从原序列中删除若干元素(可以不删除任何元素),且保持剩余元素的相对顺序不变而得到的序列。换句话说,序列 a 是序列 b 的子序列,当且仅当存在一个单调递增的索引序列 i1,i2,…,in 满足 1≤i1<i2<⋯<in≤m,且对于每个 k(1≤k≤n),都有 ak=bik。
题目描述:
给定两个整数序列 a=a1,a2,…,an 和 b=b1,b2,…,bm,请你判断 a 是否为 b 的子序列。
子序列是指一个序列从原序列中删除一些元素(也可以不删除)后,剩下的元素的顺序保持不变。换句话说,序列 a 是序列 b 的子序列,当且仅当存在一个单调递增的索引序列 i1,i2,…,in 满足 1≤i1<i2<⋯<in≤m,且对于每个 k (1≤k≤n),都有 ak=bik。
你需要判断序列 a 是否是序列 b 的子序列。
输入
- 第一行输入两个整数 n 和 m(1≤n≤m≤1000),表示序列 a 和序列 b 的长度。
- 第二行输入 n 个整数 a1,a2,…,an,表示序列 a。
- 第三行输入 m 个整数 b1,b2,…,bm,表示序列 b。
输出
如果序列 a 是序列 b 的子序列,输出 YES
,否则输出 NO
。
示例
输入 1
3 5
1 3 5
1 2 3 4 5
输出 1
YES
输入 2
3 5
1 3 6
1 2 3 4 5
输出 2
NO
样例1说明:
因为a数组[1,3,5]在b数组中对应的下标为1,3,5符合递增顺序且都能找到所以是其子序列