判断子序列算法

双指针算法
1.j指针用来扫描整个b数组，i指针用来扫描a数组。若发现a[i] == b[j]，则让i指针后移一位。
2.整个过程中，j指针不断后移，而i指针只有当匹配成功时才后移一位，若最后若i == n，则说明匹配成功。

为什么双指针做法是正确的？
整个过程中j指针不断扫描b数组并且向后移动，相当于不断给i指针所指向的a数组创建匹配的机会，只有匹配成功时i指针才会向后移动一位，当i == n时，说明全部匹配成功。

#include
#include
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
int n,m;
scanf(“%d%d”,&n,&m);
for(int i = 0;i < n; i++) scanf(“%d”,&a[i]);
for(int j = 0;j < m; j++) scanf(“%d”,&b[j]);

int i = 0;
for(int j = 0;j < m; j++)
{
    if(i < n&&a[i] == b[j])  i++;
}
if(i == n) puts("Yes");
else puts("No");
return 0;
1
2
3
4
5
6
7
8

}

题目描述
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

输入格式
第一行包含两个整数 n,m。

第二行包含 n 个整数，表示 a1,a2,…,an。

第三行包含 m 个整数，表示 b1,b2,…,bm。

输出格式
如果 a 序列是 b 序列的子序列，输出一行 Yes。

否则，输出 No。

数据范围
1≤n≤m≤105,
−109≤ai,bi≤109
输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
Yes

C++ 代码
#include
#include
#include
using namespace std;
// 新增的双指针模板题
// 基本思路就是遍历一遍“子序列” ，
// 看看其每一个元素另一个数组中是不是在都有各自的下标
// 且下标要呈递增趋势，这就有了单调性 可以用双指针
int main (){
int n,m,i,j;
scanf (“%d%d”,&n,&m);
int a[n],b[m];
for (i = 0;i < n;i++) scanf (“%d”,&a[i]);
for (j = 0;j < m;j++) scanf (“%d”,&b[j]);
i=0,j=0;
//记得复原下ij
while (i < n&&j < m){
if (a[i] == b[j]) i++;
j++;
//这个循环可理解为 对于a[i]
//b从j开始遍历 直到a[i] =b[j]了，让i+=1
//对于新的a[i],重复上行过程
//如此一来实质上就是以a[i]是否=b[j] 遍历了一遍b，注意是一遍
//期间若a[i] == b[j]了 更新ai继续遍历
}
if (i == n) printf (“Yes\n”);
//从上面的循环出来了 若a[i]遍历完了(i == n)
//就说明a是子序列 反之就不是
else printf (“No”);
return 0;
}

算法基础课笔记and题解汇总
算法基础课笔记and题解汇总

笔记：
到此双指针部分就结束啦！真开心
这题就是和归并排序一样的模式：指向两个序列的双指针算法。（其实是单指针吧。。。）
因为序列是有序的，所以我们只要从头往后扫描b数组，只要有一个a中的元素匹配不上，就是“失配”。
否则是匹配的。

代码：

#include
using namespace std;
int n, m, a[100010], b[100010];
int main() {
scanf(“%d%d”, &n, &m);
for (int i = 1; i <= n; i++) scanf(“%d”, &a[i]);
for (int j = 1; j <= m; j++) scanf(“%d”, &b[j]);
int j = 1;
for (int i = 1; i <= n; i++) {
while (b[j] != a[i] && j <= m) j++;
if (j > m) {puts(“No”); return 0;}
j++;
} puts(“Yes”);
return 0;
}
1 评论

提交评论

@Chase 1个月前 回复
#include
#include
#include
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
int n,m;

int main()
{
scanf(“%d%d”, &n, &m);
for (int i = 0; i < n; i ++ )
{
scanf(“%d”, &a[i]);
}
for (int j = 0; j < m; j ++ )
{
scanf(“%d”, &b[j]);
}
bool flag = true;
for (int i = 0,j = 0; i < n; i ++,j ++) // 相等时，i和j同步+1即可
{
while(j < m && b[j] != a[i]) j ++; // 不相等的时候：j后移找到第一个相等的
if(j == m) { // 如果未找到
cout << “No” << endl;
flag = false;
break;
}
}
if (flag)
cout << “Yes” << endl;
return 0;
}