题解

题目描述

给定两个整数序列 $a = a_1, a_2, \dots, a_n$ 和 $b = b_1, b_2, \dots, b_m$，请你判断 $a$ 是否为 $b$ 的子序列。

子序列的定义： 子序列是指一个序列从原序列中删除一些元素（也可以不删除）后，剩下的元素的顺序保持不变。换句话说，序列 $a$ 是序列 $b$ 的子序列，当且仅当存在一个单调递增的索引序列 $i_1, i_2, \dots, i_n$ 满足 $1 \leq i_1 < i_2 < \dots < i_n \leq m$，且对于每个 $k \ (1 \leq k \leq n)$，都有 $a_k = b_{i_k}$。

思路解析

要判断序列 a 是否是序列 b 的子序列，可以采用双指针的方法。具体步骤如下：

1. 初始化指针：

   • 设置指针 i 指向序列 a 的第一个元素（i = 0）。
   • 设置指针 j 指向序列 b 的第一个元素（j = 0）。

2. 遍历序列：

   • 逐一比较序列 a 和序列 b 中当前指针所指向的元素。
   • 如果 a[i] == b[j]，说明在序列 b 中找到了序列 a 的一个匹配元素，此时将指针 i 向后移动一位，继续匹配序列 a 中的下一个元素。

   if a[i] == b[j]:
       i += 1  # 找到匹配的元素，移动 a 的指针
   

   • 无论是否匹配，都将指针 j 向后移动一位，继续在序列 b 中寻找下一个可能的匹配。

   j += 1  # 无论是否匹配，b 的指针都要移动
   

3. 判断结果：

   • 如果指针 i 最终等于 n，说明序列 a 的所有元素都在序列 b 中按顺序找到了对应的位置，因此 a 是 b 的子序列，输出 YES。
   • 如果指针 j 遍历完序列 b 后，指针 i 还未到达序列 a 的末尾，说明序列 a 不是序列 b 的子序列，输出 NO。

   if i == n:
       print("YES")
   else:
       print("NO")
   

Python 代码实现

def is_subsequence(a, b):
    i, j = 0, 0  # 初始化指针 i 和 j
    n, m = len(a), len(b)

    # 使用双指针判断子序列
    while i < n and j < m:
        if a[i] == b[j]:  # 如果匹配，移动 a 的指针
            i += 1
        j += 1  # 无论是否匹配，b 的指针都要移动

    # 判断是否匹配完所有元素
    if i == n:
        return "YES"
    else:
        return "NO"

# 主函数，读取输入
if __name__ == '__main__':
    n, m = map(int, input().split())  # 读取序列长度
    a = list(map(int, input().split()))  # 读取序列 a
    b = list(map(int, input().split()))  # 读取序列 b

    print(is_subsequence(a, b))

说明

1. is_subsequence 函数：

   • 该函数接收两个参数 a 和 b，分别表示两个整数序列。
   • 初始化两个指针 i 和 j，分别指向序列 a 和 b 的第一个元素。
   • 通过比较 a[i] 和 b[j] 来判断当前元素是否匹配。如果匹配，则指针 i 向右移动，表示序列 a 的当前元素已被匹配；无论匹配与否，指针 j 总是向右移动，表示继续在序列 b 中查找下一个元素。
   • 如果指针 i 遍历完整个序列 a，即 i == n，说明 a 是 b 的子序列，返回 "YES"；否则返回 "NO"。

2. 主函数：

   • 读取输入的整数序列，并调用 is_subsequence 函数判断 a 是否是 b 的子序列。

示例

输入：

3 5
1 3 5
1 2 3 4 5

输出：

YES

解释

我们需要判断序列 a = [1, 3, 5] 是否是序列 b = [1, 2, 3, 4, 5] 的子序列。为此，我们使用双指针的方法来模拟匹配过程。

指针运动过程总结：

通过以上步骤，我们成功匹配了序列 a 的所有元素，验证了 a 是 b 的子序列。

题目描述：

给定两个整数序列 $a = a_1, a_2, \dots, a_n$ 和 $b = b_1, b_2, \dots, b_m$，请你判断 $a$ 是否为 $b$ 的子序列。

子序列是指一个序列从原序列中删除一些元素（也可以不删除）后，剩下的元素的顺序保持不变。换句话说，序列 $a$ 是序列 $b$ 的子序列，当且仅当存在一个单调递增的索引序列 $i_1, i_2, \dots, i_n$ 满足 $1 \leq i_1 < i_2 < \dots < i_n \leq m$，且对于每个 $k \ (1 \leq k \leq n)$，都有 $a_k = b_{i_k}$。

你需要判断序列 $a$ 是否是序列 $b$ 的子序列。

输入

• 第一行输入两个整数 $n$ 和 $m$（$1 \leq n \leq m \leq 1000$），表示序列 $a$ 和序列 $b$ 的长度。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列 $a$。
• 第三行输入 $m$ 个整数 $b_1, b_2, \dots, b_m$，表示序列 $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$符合递增顺序且都能找到所以是其子序列