1.最长连续不重复子序列
思路：
找到i,j的单调性，统一向后移动，使时间复杂度为O（2n）
枚举i，每次看j是否需要向后走，得到最长的长度
#include <bits/stdc++.h> using namespace std; const int N = 100010; int a[N],flag[N]; int main() { int n; cin>>n; for(int i=0;i<n;i++) scanf("%d",&a[i]); int ans=0; for(int i=0,j=0;i<n;i++) { flag[a[i]]++; while(flag[a[i]]>1) { flag[a[j]] --; j++; } ans=max(ans,i-j+1); } cout<<ans; return 0; }
2.数组元素的目标和
输入样例：
4 5 6 1 2 4 7 3 4 6 8 9
输出样例：
1 1
思路：
双指针算法对于朴素做法的优化：
寻找单调性
i从 0开始 从前往后遍历
j从 m - 1开始 从后向前遍历
对于每个i，找到一个j，使得a[i]+b[j]>x，且j最靠左
#include <bits/stdc++.h> using namespace std; const int N = 100010; int a[N],b[N]; int n,m,x; int main() { cin>>n>>m>>x; for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<m;i++) scanf("%d",&b[i]); for(int i=0,j=m-1;i<n;i++) { while(j>=0 && a[i]+b[j]>x) j--; if(a[i]+b[j]==x) { cout<<i<<' '<<j; break; } } return 0; }
3.判断子序列
给定一个长度为 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。
输入样例：
3 5 1 3 5 1 2 3 4 5
输出样例：
Yes
思路：
遍历b数组，在a数组中指针找到匹配的数字， 如果a数组全部匹配成功，则输出Yes，否则输出No
代码：
#include <bits/stdc++.h> using namespace std; const int N = 100010; int a[N],b[N]; int main() { int n,m; cin>>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) break; if(a[i]==b[j]) i++; } if(i==n) cout<<"Yes"; else cout<<"No"; return 0; }
