双指针

技术双指针 双指针双指针799. 最长连续不重复子序列
给定一个长度为 \(n\) 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 \(n\)。
第二行包含

双指针

双指针

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

(0)

相关推荐

  • zookeeper和eureka使用场景(eureka与zookeeper差别)

    技术如何进行ZooKeeper与Eureka的比较如何进行ZooKeeper与Eureka的比较,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获

    攻略 2021年12月24日
  • oracle11g dataguard如何切换

    技术oracle11g dataguard如何切换这篇文章主要介绍“oracle11g dataguard如何切换”,在日常操作中,相信很多人在oracle11g dataguard如何切换问题上存在疑惑,小编查阅了各式

    攻略 2021年11月11日
  • Java中如何把二叉搜索树转换为累加树

    技术Java中如何把二叉搜索树转换为累加树这篇文章主要介绍了Java中如何把二叉搜索树转换为累加树,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。一、题目给

    攻略 2021年11月2日
  • 如何解析JDK 6中Java Console类功能的概览

    技术如何解析JDK 6中Java Console类功能的概览本篇文章给大家分享的是有关如何解析JDK 6中Java Console类功能的概览,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,

    攻略 2021年11月20日
  • 怎么使用JavaScript中的sort

    技术怎么使用JavaScript中的sort本篇内容主要讲解“怎么使用JavaScript中的sort”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“怎么使用JavaScrip

    攻略 2021年11月20日
  • 怎么查询mysql的编码格式(mysql编码查看方式)

    技术mysql怎么查询编码这篇文章主要为大家展示了“mysql怎么查询编码”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“mysql怎么查询编码”这篇文章吧。

    攻略 2021年12月14日