双指针-快慢指针（龟兔指针）-程序员充电站

快慢指针本质上是一种思想，而非一种算法，就和贪心一样，不能把其简单地看作一种算法。

概念

这里的指针并非C和C++中的指针，你可以理解为数组下标或者类似的东西。

快指针：快速遍历并检测符合条件的数据，先行一步查找满足前置条件的数据

慢指针：维护已处理数据的边界，即对已满足条件数据的维护

双指针可以帮我们降低遍历的次数，加快程序运行速度，降低时间复杂度。

例题

有序数组去重

将一个已经排序好的数组去重，如1，2，3，3，3，4，5在去重后变成1，2，3，4，5

代码部分

常规做法

#include<iostream> using namespace std; int main(){ int num[7] = {1 , 2 , 3 , 3 , 3 , 4 , 5}; int cnt = 0; //计算重了几个 for(int i = 0 ; i < 7 - cnt ; i ++){ if(i != 0 && num[i] == num[i - 1]){ cnt ++; i --; for(int j = i ; j < 7 - cnt ; j++){ num[j] = num[j + 1]; } } } for(int i = 0 ; i < 7 - cnt ; i ++){ cout << num[i] << ' '; } cout << endl; return 0; }

但是这样双重嵌套的情况下，如果数组比较长，就会导致代码的运行效率异常低下。所以我们将使用双指针。

快慢指针写法

我们将转换思考方式，我们现在想要去重，就只需要把没出现过的暂时存起来，这样就不需要嵌套遍历（其实是空间换时间的思想）

#include<iostream> using namespace std; int main(){ int num[7] = {1 , 2 , 3 , 3 , 3 , 4 , 5}; int temp[7] = {}; //定义一个零时数组 temp[0] = num[0]; int j = 0; //慢指针，即temp的数组边界（下标） for(int i = 0 ; i < 7 ; i++){ if(temp[j] != num[i]){ //遍历存储 temp[j + 1] = num[i]; j++; } } for(int i = 0 ; i < j + 1 ; i++){ cout << temp[i] << ' '; } cout << endl; return 0; }

肥肠简单的一个例子，相信没有看这个文章大家也可以想到这种方法。

当然，也可以不用temp[j] != num[i]这种判断方式，由于数组本身已经有序，所以可以直接将相同的右边界放入temp数组中，如2，2，2，3的时候判断快指针所指数和下一个数是否相同，不同则将该数放入。

当然，我们也可以对内存空间进一步优化，我们舍弃temp数组，直接将两个指针都用在num上

完全体的快慢指针

#include<iostream> using namespace std; int main(){ int num[7] = {1 , 2 , 3 , 3 , 3 , 4 , 5}; int j = 0; //慢指针，数组边界 for(int i = 0 ; i < 7 - 1 ; i++){ if(num[i] != num[i + 1]){ //边界判断，如果到边界则进行存储 num[j] = num[i]; j++; } } if(num[j] != num[6]){ num[j] = num[6]; //由于循环的时候我们将最后一位舍弃，所以这里我们要放回 j++; } for(int i = 0 ; i < j ; i++){ cout << num[i] << ' '; } cout << endl; return 0; }

如此一来，我们连temp的空间都省下来了

原地删除

如数组1，2，3，4，5，6，2，2，2，3，1，4，5

我们想把2全都删掉的同时保证数组成员之间的相对关系保持不变

同样的，我们可以用常规方法来实现，但是常规方法不但麻烦而且复杂度也比叫高，所以我们使用快慢指针来实现数组成员的删除

代码实现

#include<iostream> using namespace std; int main(){ int num[13] = {1,2,3,4,5,6,2,2,2,3,1,4,5}; int j = 0; //慢指针 for(int i = 0 ; i < 13 ; i++){ if(num[i] != 2){ num[j] = num[i]; j++; } } for(int i = 0 ; i < j ; i++){ cout << num[i] << ' '; } cout << endl; return 0; }

~~代码简介而优雅~~

最长连续不重复子序列

洛谷U224090

题目描述：给定长度为 n 的整数序列，找出最长的不包含重复的数的连续区间，输出它的长度

输入格式：第一行包含整数n（1 <= n <= 100000）

第二行包含 n 个整数（均在0~10^5范围内），表示整数序列

输入

5
1 2 2 3 5

输出

3

对于这道题目，如果我们直接使用暴力做法，就会生成三层循环，导致超时。

暴力写法

#include<iostream> using namespace std; const int N = 1e5 + 10; int arr[N]; int main(){ int n; cin >> n; for(int i = 0 ; i < n ; i++){ cin >> arr[i]; } int maxlen = 0; //最长长度 for(int i = 0 ; i < n - 1 ; i++){ int len = 1; //i和j的起始长度相差1 for(int j = i + 1 ; j < n ; j++){ int flag = 0; //标记，0为范围内无重复，1为有重复 for(int k = i ; k < j ; k++){ //从头到尾查一遍 if(arr[k] == arr[j]){ flag = 1; break; } } if(flag) break; else len++; } if(len > maxlen){ maxlen = len; } } cout << maxlen << endl; return 0; }

由于太过暴力，十个测试点我们只能通过4个，剩下的全部都超时了。所以使用暴力来解决这个问题是不恰当的

此时的时间复杂度为O()，所以我们要对这段代码进行优化

第一次优化

对最内层循环进行优化，优化其判断区间是否有重复元素的逻辑

这里我们首先采取空间换时间的方法来降低时间复杂度，即利用计数排序的逻辑来判断这段连续子序列中每个元素的出现次数

#include<iostream> #include<cstring> using namespace std; const int N = 1e5 + 10; int arr[N]; int main(){ int n; cin >> n; for(int i = 0 ; i < n ; i++){ cin >> arr[i]; } int maxlen = 0; //最长长度 for(int i = 0 ; i < n - 1 ; i++){ int cnt[N]; // 定义统计出现次数的数组 memset(cnt , 0 , sizeof(cnt)); // 清空cnt数组为0 int len = 0; for(int j = i ; j < n ; j++){ if(cnt[ arr[j] ] == 0){ len++; cnt[ arr[j] ] = 1; }else{ break; } } if(len > maxlen){ maxlen = len; } } cout << maxlen << endl; return 0; }

在进行一次优化后，我们的时间复杂度下降到了O()

然后我们发现十个测试点就全都通过了

过不去的多提交几遍就过了(bushi)

第二次优化

但是O()的时间复杂度还是相当大，如果题目给出的 n 再大几个数量级，那么我们也无法顺利通过这道题，所以我们还需要进行再次优化

这一次，我们将根据题目的本质来进行优化，题目的要求是找出最长的不重复子序列，所以当出现重复的数时，我们直接把慢指针移到出现过的数的后一位继续遍历

1，2，5，6，7，6，9，10
我们定义两个指针 i 和 j ，i 为慢指针
当 i 为0的时候，我们发现当 j 等于 5 的时候，出现了重复的数据，这个时候我们直接将 i 移到第一个 6 后方，也就是让 i 等于 3 ，然后让 j 继续遍历

这个方法成立的原因在于：当 i 在第一个 6 之前时，无论 i 如何移动， j 都无法越过第二个 6 ，所以我们便让 i 直接到第一个 6 后方

#include<iostream> #include<cstring> using namespace std; const int N = 1e5 + 10; int arr[N]; int main(){ int n; cin >> n; for(int i = 0 ; i < n ; i++){ cin >> arr[i]; } int maxlen = 0; //最长长度 for(int i = 0 ; i < n - 1 ; i++){ //慢指针 int cnt[N] = {0} , len = 0; // 统计数据出现次数 for(int j = i ; j < n ; j++){ //快指针 if(cnt[arr[j]] == 0){ cnt[arr[j]] = 1; len++; }else{ for(int k = i ; k <= j ; k++){ //查找第一次出现位置，直接把i移到次位置后 if(arr[k] == arr[j]){ i = k; // 注意，不需要加一，当外层循环结束后，i会自动加1 break; } } break; } } if(len > maxlen){ maxlen = len; } } cout << maxlen << endl; return 0; }

虽然看起来我们的循环变成了三层，但是我们利用内层循环减少了最外层循环，所以从整体上看我们的代码的时间复杂度还是在下降的

当然，嵌套的存在还是为我们的代码增添了不确定性，所以我们可以最终优化将代码变为单层循环

最终优化

#include<iostream> #include<cstring> using namespace std; const int N = 1e5 + 10; int arr[N]; int main(){ int n; cin >> n; for(int i = 0 ; i < n ; i++){ cin >> arr[i]; } int maxlen = 0; //最长长度 int i = 0; // 慢指针 int cnt[N] = {0}; // 统计数据出现次数 for(int j = 0 ; j < n ; j++){ //快指针 cnt[arr[j]]++; //当前位置的数统计次数加1 while(cnt[arr[j]] > 1){ // 循环直到当前位置的数统计次数降到1 cnt[arr[i]]--; i++; } if(j - i + 1 > maxlen){ maxlen = j - i + 1; } } cout << maxlen << endl; return 0; }

通过这次优化，我们最终将时间复杂度降到了O(n)