最长连续不重复子序列
输入样例
5
1 2 2 3 5
输出样例
3
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],s[N];//s数组用来记录每个数出现的次数
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int res;//记录最长不连续区间
for (int i = 0, j = 0; i < n; i++)
{
s[a[i]]++;//出现的数加一
while (s[a[i]] > 1)
{
s[a[j]]--;//指针j所在的数减一
j++;//指针j先后以一位
}
res = max(res, i - j + 1);
}
printf("%d", res);
return 0;
}
数组元素的目标和
输入样例
4 5 6 //数列a长度 数列b长度 目标值x
1 2 4 7 //数列a
3 4 6 8 9 //数列b
输出样例
1 1 //使a[i]+b[j]=x
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N], b[N];
int main()
{
int n, m, x;
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]);
int i, j;
for (i = 0, j = m-1;i < n; i++)//i从前往后,j从后往前
{
while (j >= 0 && a[i] + b[j] > x)//如果结果大于x, j往前移一位
j--;
if (a[i] + b[j] == x)
break;
}
printf("%d %d", i, j);
return 0;
}
判断子序列(按原有次序排列)
输入样例
3 5
1 3 5
1 2 3 4 5
输出样例
Yes
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
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 i = 0; i < m; i++)
scanf("%d", &b[i]);
int i, j;
while (i < n && j < m)
{
if (a[i] == b[j])//如果相等,a序列指针向后移一位
i++;
j++;//b序列指针每次都要向后移动一位
}
if (i == n)//a序列完全匹配
printf("Yes");
else
printf("No");
return 0;
}