#17. 判断子序列
判断子序列
给定一个长度为 的整数序列 以及一个长度为 的整数序列 。
请你判断 序列是否为 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列,例如序列 是序列 的一个子序列。
输入格式
第一行包含两个整数 。
第二行包含 个整数,表示 。
第三行包含 个整数,表示 。
输出格式
如果 序列是 序列的子序列,输出一行 Yes。
否则,输出 No。
数据范围
,
输入样例:
3 5
1 3 5
1 2 3 4 5
输出样例:
Yes
样例:基础正确用例(典型子序列)。
n=m 完全相同:必须输出 Yes;卡把“子序列”误当“真子串/必须跳过元素”的错误。
n=m 仅一项不同:卡只比较长度/只比前几项/漏检最后差异。
n=1 且 b 中多次出现:卡只检查一次、或错误地要求“连续出现”。
n=1 且 b 中不存在:基础反例;卡默认输出 Yes/未找到也算找到。
顺序不一致(a 元素都在 b 里但次序不对):卡把“子序列”写成“子集/只看出现次数”。
a 有大量重复但 b 次数不够:卡只判断“值出现过”而不计数/不推进指针。
a 重复且 b 次数刚好够且分散:卡错误地要求连续、或匹配策略不正确。
全负数正确匹配:卡把负数处理错(比如用 unsigned、或读入/比较错误)。
负数混合且缺项:卡“只要前面能匹配就认为 Yes”、或漏判中间元素。
a 是 b 的前缀:卡一些写法只会在中间跳而不会处理前缀/边界。
a 是 b 的后缀:卡没扫到末尾/提前结束。
必须用到 b 的最后一个元素才能匹配:重点卡“扫描 b 没到最后”“循环条件写错(i<n && j<m 之类)”。
几乎全匹配,只缺一个中间元素(n 接近 m):卡 off-by-one、指针推进错导致漏匹配。
极值 -1e9 与 1e9:卡 int 溢出/比较边界(虽一般 int 足够,但有些语言/写法会出错)。
同极值但顺序相反:卡把“集合匹配”当“序列匹配”。
交替重复序列(需要贪心地从左到右选):卡错误回退/错误地“匹配后不推进”导致乱序。
元素及次数看似够,但顺序导致不可能:卡只看计数不看相对顺序。
m 很大、n 很小、匹配点很稀疏且包含最后位置:卡性能(O(nm) 会慢)、以及“必须扫到接近末尾”。
与 19 类似但最后一个目标不存在:卡“找到前几个就直接 Yes”、或末尾漏判。
最小规模 n=m=1 且相等:卡边界初始化/循环不进导致错误输出。
最小规模 n=m=1 且不等:卡边界判断反例。
b 单调下降,a 单调上升:卡一些错误假设(比如以为有序就能二分/误用双指针方向)。
b 重复很多,a 需要选择“合适的后续重复”才能成功:卡“总是匹配到错误位置后无法继续”的非标准写法(正确双指针没问题)。
与 24 同 b,但 a 顺序换一下变成不可能:卡“只要值都出现过就 Yes”、以及不正确的匹配策略。