双指针算法
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;
}
题目描述
给定一个长度为 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 <bits/stdc++.h> 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; }
