双指针
双指针
799. 最长连续不重复子序列
给定长度为\(n\)的整数序列，请找出没有重复数字的最长连续间隔，并输出其长度。
输入格式
第一行包含整数\(n\)。
第二行包含\(n\)个整数(都在\ (0 \ sim10 5 \)的范围内)，表示整数序列。
输出格式
一行包含一个整数，表示没有重复数字的最长连续间隔的长度。
数据范围
\(1n10^5\)
输入样例：
五
1 2 2 3 5
输出样例：
三
对于间隔\((i，j)\)、固定\(j\)和移动\(i\)，维护间隔中的数字不重复。
时间复杂度：\(O(n)\)
代码
#includebits/stdc。h
使用命名空间标准；
int n，a[100005]，CNT[100005]；
int main()
{
scanf(‘%d ‘，n)；
for(int I=1；I=n；i )scanf(‘%d ‘，a[I])；
int RES=0；
for(int i=1，j=1；I=n；(一)
{
CNT[a[I]]；
while(jicnt[a[I]]1)CNT[a[j]]-；
res=max(res，I-j 1)；
}
printf(“% d”，RES)；
返回0；
}
800. 数组元素的目标和
给定两个按升序排列的有序数组和一个目标值。
数组下标从\(0\)开始。
请找出满足\(A[i] B[j]=x\)的数字对\((i，j)\)。
确保数据有唯一的解决方案。
输入格式
第一行包含三个整数\(n，m，x\)，分别表示\(A\)、长度\(B\)和目标值\(x\)。
第二行包含代表数组的\(n\)个整数。
第三行包含代表数组的\(m\)个整数。
输出格式
一行，包含两个整数\(i\)和\(j\)。
数据范围
数组长度不超过\(10 ^ 5 \)。
同一数组中的元素不同。
\(1数组元素10 ^ 9 \)
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
对于固定\(i\)，找出满足\(a[i] b[j]\leq x\)的\(j\)
时间复杂度：\(O(n ^ m)\)
代码
#includebits/stdc。h
使用命名空间标准；
int n，m，x，a[100005]，b[100005]；
int main()
{
scanf(‘%d%d%d ‘，n，m，x)；
for(int I=1；I=n；i )scanf(‘%d ‘，a[I])；
for(int I=1；I=m；i )scanf(‘%d ‘，b[I])；
for(int i=1，j=m；I=n；(一)
{
而(j=1a[I]b[j]x)j-；
if(j=1a[i] b[j]==x)
printf(‘%d %d ‘，i-1，j-1)；
}
返回0；
}
2816. 判断子序列
给定长度为\(n\)的整数序列\(a_1，a_2，…，a_n\)和长度为\(m\)的整数序列\(b_1，b_2，…，b_m\)。
请判断\(a\)序列是否是\(b\)序列的子序列。
子序列是指序列中的某些项目按原始顺序排列的序列。例如，序列\({a_1，a_3，a_5}\)是序列\({a_1，a_2，a_3，a_4，a_5}\)的子序列。
输入格式
第一行包含两个整数\(n，m\)。
第二行包含代表\(a_1，a_2，…，a_n\)的\(n\)个整数。
第三行包含代表\(b_1，b_2，…，b_m\)的\(m\)个整数。
输出格式
如果\(a\)序列是\(b\)序列的子序列，则输出一行“是”。
否则，输出否.
数据范围
\(1nm10^5\)，
\(?10^9a_i,b_i10^9\)
输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
是
时间复杂度：\(O(n ^ m)\)
代码
#includebits/stdc。h
使用命名空间标准；
int n，m，a[100005]，b[100005]；
int main()
{
scanf(‘%d%d ‘，n，m)；
for(int I=1；I=n；i )scanf(‘%d ‘，a[I])；
for(int I=1；I=m；i )scanf(‘%d ‘，b[I])；
int j=1；
for(int I=1；I=m；(一)
{
if(j=nb[I]==a[j])j；
}
看跌期权(j==n1 ‘ Yes ‘ : ‘ No ‘)；
返回0；
}
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/92784.html