2816. 判断子序列
摘要
Title: 2816. 判断子序列
Tag: 双指针
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
2816. 判断子序列
-
题意
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。 -
思路
遍历两个数组，看是否匹配上，指定一个指针不动，移动另一个指针，直到两者数相等
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24'''
Author: NEFU AB-IN
Date: 2022-02-23 10:33:49
FilePath: \ACM\Acwing\2816.py
LastEditTime: 2022-02-23 10:38:16
'''
N = int(1e5 + 100)
a = [0] * N
b = [0] * N
n, m = map(int, input().split())
a[1:] = map(int, input().split())
b[1:] = map(int, input().split())
j = 1
for i in range(1, n + 1):
while j <= m and b[j] != a[i]:
j += 1
if j > m:
print("No")
exit(0)
else:
j += 1
print("Yes")另一版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25'''
Author: NEFU AB-IN
Date: 2022-02-23 10:33:49
FilePath: \ACM\Acwing\2816.py
LastEditTime: 2022-02-23 10:38:16
'''
N = int(1e5 + 100)
a = [0] * N
b = [0] * N
n, m = map(int, input().split())
a[1:] = map(int, input().split())
b[1:] = map(int, input().split())
i, j = 1, 1
while i <= n and j <= m:
if a[i] == b[j]:
i += 1
j += 1
if i == n + 1:
print("Yes")
else:
print("No")