慈溪企业网站,网站备案要营业执照原件吗,潍坊网站开发公司,领地网做网站咋加文章目录 最长列许不重复子序列思路#xff1a;此题思路;解题代码 原题链接 最长列许不重复子序列
给定一个长度为 n 的整数序列#xff0c;请找出最长的不包含重复的数的连续区间#xff0c;输出它的长度。
输入格式 第一行包含整数 n 。
第二行包含 n 个整数#xff08;均… 目录 最长列许不重复子序列思路此题思路;解题代码 原题链接 最长列许不重复子序列
给定一个长度为 n 的整数序列请找出最长的不包含重复的数的连续区间输出它的长度。
输入格式 第一行包含整数 n 。
第二行包含 n 个整数均在 0∼105 范围内表示整数序列。
输出格式 共一行包含一个整数表示最长的不包含重复的数的连续区间的长度。
数据范围 1≤n≤105 输入样例 5 1 2 2 3 5 输出样例 3
思路
双指针题目的核心思想就是把双重循环的暴力做法利用某种性质优化到o(n) 双指针题目的解题模版
for(int i0,j0;in;i)
{while( jicheck(i,j))j;//每道题的具体逻辑
}此题的两种做法
//暴力做法 O(n^2)
//先枚举末尾
for(int i0;in;i)
{//再枚举起点for(int j0;ji;j)//检查一下起点和终点是否满足题目要求if(!check(j,i){//更新最大序列res max(res,j-i1);}
}check()表示查看j i之间是否有重复元素
//双指针做法
for(int i0,j0;in;i)
{while(ji !check(j,i))j;res max(i-j1,res);
}此题思路;
维护两个指针去遍历此数组的部分区域 i和j都不断往后移动 为什么j不往前移动? 因为 如果j往前移动 而i往后移动 j 和 i区间被扩大了而子区间内有重复元素 那么此大区间也必定有重复元素
解题代码
#include iostreamusing namespace std;const int N 100010;int n;
//一个表示接入的数组 一个表示j i 区间内数字的数量
int q[N], s[N];int main()
{scanf(%d, n);for (int i 0; i n; i ) scanf(%d, q[i]);int res 0;for (int i 0, j 0; i n; i ){s[q[i]] ;//数字的数量如果大于1 表示有重复元素 需要将j往后移动 同时j i 区间内当前j下标的数字数量-1while (j i s[q[i]] 1) s[q[j ]] -- ;res max(res, i - j 1);}cout res endl;return 0;
}
