一、最长连续不重复子序列
算法模板：
for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 } 常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
例题：
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤10^5
输入样例：
5 1 2 2 3 5
输出样例：
3
输入
10 9 3 6 9 5 10 1 2 3 9
输出
7
标准答案
7
图解：
此时s[a[i]]出现俩次 (a[i]=2)执行while循环
while (s[a[i]] > 1)
{
s[a[j]] --; j++;
}
此后均出现一次，j的位置不变
#include<iostream> using namespace std; const int N=100010; int n; int s[N],a[N]; int main() { cin>>n; for(int i=0;i<n;i++)cin>>a[i]; int res=0; for(int i=0,j=0;i<n;i++) { s[a[i]]++; while(j<i&&s[a[i]]>1) { s[a[j]]--;//将重复的次数减掉，才能跳出循环 j++; } res=max(res,i-j+1); } cout<<res<<endl; return 0; }
例题:
1.数组元素的目标和
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m个整数，表示数组 B。
输出格式
共一行，包含两个整数 i和 j。
数据范围
数组长度不超过 10^5。
同一数组内元素各不相同。
1≤数组元素≤10^9
输入样例：
4 5 6 1 2 4 7 3 4 6 8 9
输出样例：
1
思路：
为了减少循环，采用了两个指针来保证能遍历符合要求的所有数；
i指针从A数组的头开始，此时a[i]最小；
j指针从B数组的尾开始，此时b[j]最大；
在i = 0 时，判断a[i] + b[j] 的值，如果大于x，j- -；
也就是说b[j]的值一直在减小；
那么当a[i] + b[j] 的值第一次小于x时，j指针的左边的数与a[i]相加一定都小于x了；那么我们只能增大a[i]的值；
于是i ++;
自此开始反复循环,如果a[i] + b[j] 大于x，就减小b[j]（相当于将j指针左移）反之，就增大a[i]（相当于i指针右移）
这样，一定保证了每一个符合要求的两个数都能加一遍，判断是不是和等于x。
#include<iostream> using namespace std; const int N=100010; int n,m,x; int a[N],b[N]; int main() { cin>>n>>m>>x; for(int i=0;i<n;i++)cin>>a[i]; for(int j=0;j<m;j++)cin>>b[j]; 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<<endl; } return 0; }
2.判断子序列
定一个长度为 n的整数序列 a1,a2,…,an 以及一个长度为 m的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5}{1,3,5} 是序列 {a1,a2,a3,a4,a5}{1,2,3,4,5} 的一个子序列。
输入格式
第一行包含两个整数 n,m。
第二行包含 n 个整数，表示 a1,a2,…,an。
第三行包含 m个整数，表示 b1,b2,…,bm。
输出格式
如果 a 序列是 b序列的子序列，输出一行 Yes。
否则，输出 No。
数据范围
1≤n≤m≤10^5
−10^9≤ai,bi≤10^9
输入样例：
3 5 1 3 5 1 2 3 4 5
输出样例：
Yes
思路：
整个过程中j指针不断扫描b数组并且向后移动，相当于不断给i指针所指向的a数组创建匹配的机会，只有匹配成功时i指针才会向后移动一位，当i == n时，说明全部匹配成功。
#include<iostream> using namespace std; const int N=100010; int n,m; int a[N],b[N]; int main() { cin>>n>>m; for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<m;i++)cin>>b[i]; int i=0,j=0; while(i<n&&j<m) { if(a[i]==b[j])i++; j++; } if(n==i)puts("Yes"); else puts("No"); return 0; }
