双指针算法的一个简单题解

打印 上一主题 下一主题

主题 1794|帖子 1794|积分 5382

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目是这样的:
给定一个长度为 n
的整数序列,请找出最长的不包罗重复的数的连续区间,输出它的长度。
输入格式
第一行包罗整数 n

第二行包罗 n
个整数(均在 0∼105
范围内),表示整数序列。
输出格式
共一行,包罗一个整数,表示最长的不包罗重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例:
5
1 2 2 3 5
输出样例:
3
这题用双指针算法,先介绍一下双指针算法,双指针算法最大的一个好处便是把时间复杂度从o(n**2)降低到o(n),这道题如果我们使用朴素的暴力枚举是可以做的,最好的枚举结果是
int res = 0
for(int i = 1;i  n;
for(int i = 0;i < n;i ++)        cin >> a;
[code]for(int i = 0,j = 0;i < n;i ++){        s[a] ++;                while(s[a] > 1)        {                s[a[j]] --;//移动j指针,直到没有重复的元素                j ++;        }//这部分代码当这次枚举的i与上一次的重复时会实行                res = max(res , i - j + 1);}cout
回复

举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

傲渊山岳

论坛元老
这个人很懒什么都没写!
快速回复 返回顶部 返回列表