AcWing 2816. 判断子序列——算法基础课题解
原文中文，约2200字，阅读约需6分钟。
📝
内容提要
给定两个整数序列a和b，判断a是否为b的子序列。如果是，输出Yes；否则，输出No。
🔎
延伸解读
双指针解法的核心逻辑
文章给出的C和Go代码都采用双指针：i指向a，j指向b。遍历b时，若a[i]等于b[j]，则i前进；无论是否匹配，j都前进。当i达到n时说明a的所有元素已按序在b中找到，输出Yes。该算法只需一次线性扫描，时间复杂度O(m)，空间复杂度O(1)，适合n,m≤10^5的数据规模。
输入处理与数据范围注意点
题目中n和m最大为10^5，元素绝对值可达10^9，因此需用能容纳大整数的类型。C代码使用int（通常足够），Go示例中一个版本用int，另一个用int64。输入可能跨行，Go的bufio按行读取并用strings.Fields分割，能稳健处理空格和换行，避免因格式问题导致读取失败。
子序列与子数组的区别
子序列只要求元素在b中按原有相对顺序出现，不要求连续。例如a={1,3,5}，b={1,2,3,4,5}，虽然3和5在b中不相邻，但顺序正确，因此是子序列。若题目要求连续，则需用子数组（连续子段）的判定方法，如滑动窗口或KMP，不能直接套用本文的双指针。
❓
Q&A
如何判断一个序列是否为另一个序列的子序列？
通过比较两个序列中的元素，检查第一个序列的所有元素是否按顺序出现在第二个序列中。
输入格式是什么样的？
输入包括两个整数n和m，接着是n个整数的序列a和m个整数的序列b。
如果序列a是序列b的子序列，输出什么？
输出Yes。
数据范围是什么？
数据范围为1≤n≤m≤10^5，−10^9≤ai,bi≤10^9。
能否提供代码实现的语言？
提供了C和Go语言的实现代码示例。
子序列的定义是什么？
子序列是序列的一部分项按原有次第排列而得的序列。
🏷️
