⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。若C++基础不牢固,可参考:10min快速回顾C++语法,进行语法复习。
????本文已收录于算法基础系列专栏: 算法基础教程 免费订阅,持续更新。
双指针算法
双指针算法的常见情况:
- 双指针在两个数组上(例如归并排序等等)
- 双指针在一个数组上
常见通用代码模板
双指针的核心思想是优化。
常见的遍历一共是双重循环,复杂度是O()
但是双指针算法虽然是看起来是双重循环,但是实际上每个指针移动的次数是不超过O(n)的,两个指针的总次数不超过O(2n)。将之前的朴素算法优化到O(n)。
举例:分行输出字符串
假设有一个字符串“acb def jhi”以空格分开,现在要将其以空格为分解,换行输出。
基本思路:采用双指针算法
首先i和j在同一起点位置,然后j进行扫描。
j停在空格分界的位置上,输出两位置之间的字符串
把指针i移动在j上。
模板应用
最长连续不重复子序列
给定一个长度为 nn 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 nn。
第二行包含 nn 个整数(均在 0∼1050∼105 范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤1051≤n≤105
输入样例:
输出样例:
朴素做法:
双指针算法模板:
双指针基本思路:
首先i循环遍历,j的含义是j最远能到什么地方,因为需要计算的是无重复的个数,因此j和i之间无重复的数。
可以证明:在i不断后移同时,j必然也是单调后移的,不可能出现j前移的情况,因为j如果前移,那么就证明刚刚最大的位置并非最优值,这与刚刚的结论矛盾。
有了单调这一层性质,就可以采用双指针这种单调队列的思想优化。因为可以使j在i遍历的时候仍然记录上次的位置。
具体条件的应用;
- 开辟一个动态数组来记录每个值出现多少次。例如原来需要判断的数组为a[n]。记录时就可以另外开辟以该值为序列号的数组S[N];
- i往后移动一格,代表有一个数进来了,即S[a[i]]++;
- j往后移动一格,代表有一个数出去了,即S[a[j]]--;
这样可以动态地统计区间内有多少个数。
- 其中如果有重复的值,一定是新加进来的a[i],那么那个值统计后,该记录数组的值大于1,那么j下次就必须去掉那个值,移动到该值之后。
这里如果j > i的时候,一定了要求,区间里一个数都没有了,就会不满足S[a[i]] > 1,因此本题这个比较条件j <= i可以不写。
代码
当数组很大的时候,可以考虑采用哈希表来实现。哈希表可以存任意量,包括字母,数字,字符串。
注意:要想采用双指针算法优化,重要的是这一种单调关系。