一、算法描述
含义
-
双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。
-
另外还可以根据序列进行区分,例如在快排中,双指针指向的是同一个序列,而归并排序中两个指针指向的是两个不同的序列。
怎么用
-
没有必要对概念区分的很清楚,只需要知道怎么使用即可。
-
首先想暴力解法,然后在暴力解法的基础之上,发现性质,进行优化。
-
通过题目来理解什么是双指针吧。
二、题目描述
给定一个长度为 (n) 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 (n)。
第二行包含 (n) 个整数(均在 (0) ~ (10 ^ 5) 范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
(1 ≤ n ≤ 10 ^ 5)
输入样例:
5
1 2 2 3 5
输出样例:
3
三、题目来源
AcWing算法基础课-799.最长连续不重复子序列
四、算法思路
-
首先暴力做法就是,枚举左端点 (l) ,枚举右端点 (r) ,然后枚举区间 ([l, r]) 判断是否有重复数字,然后更新答案,显然该做法时间复杂度会非常高,所以可以优化一下。
-
如何优化呢?
-
遍历数组 (a) 中的每一个元素 (a[i]) , 对于每一个(i),找到j使得双指针 ([j, i]) 维护的是以 (a[i]) 结尾的最长连续不重复子序列,长度为 (i – j + 1) , 将这一长度与 (res) 的较大者更新给(res)。
-
对于每一个 (i) ,如何确定j的位置:由于 ([j, i – 1]) 是前一步得到的最长连续不重复子序列,所以如果 ([j, i]) 中有重复元素,一定是 (a[i]),因此右移 (j)直到 (a[i]) 不重复为止(由于 ([j, i – 1]) 已经是前一步的最优解,此时 (j) 只可能右移以剔除重复元素 (a[i]),不可能左移增加元素,因此, (j) 具有“单调性”、本题可用双指针降低复杂度)。
五、源代码
#include
using namespace std;
const int N = 100010;
int n;
int a[N], s[N];
int main()
{
cin >> n;
for (int i = 0; i > a[i];
int res = 0;
for (int i = 0, j = 0; i 1)
{
-- s[a[j]];
++ j;
}
res = max(res, i - j + 1);
}
cout
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net