算法基础（六）| 双指针算法及模板应用

⭐写在前面的话：本系列文章旨在复习算法刷题中常用的基础算法与数据结构，配以详细的图例解释，总结相应的代码模板，同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的 C++基础的学习者。若 C++基础不牢固，可参考：10min快速回顾C++语法，进行语法复习。

🔥本文已收录于算法基础系列专栏： 算法基础教程 免费订阅，持续更新。

双指针算法

双指针算法的常见情况：

• 双指针在两个数组上（例如归并排序等等）

• 
  
  

• 双指针在一个数组上

• 
  
  

常见通用代码模板

for(i = 0, j =0; i < n; i++ ){    while(j < i && check(i,j))j++;    //再加上每道题目的具体逻辑}

双指针的核心思想是优化。

常见的遍历一共是双重循环，复杂度是 O($n^2$)

但是双指针算法虽然是看起来是双重循环，但是实际上每个指针移动的次数是不超过 O(n)的，两个指针的总次数不超过 O(2n)。将之前的朴素算法优化到 O(n)。

举例：分行输出字符串

假设有一个字符串“acb def jhi”以空格分开，现在要将其以空格为分解，换行输出。

基本思路：采用双指针算法

首先 i 和 j 在同一起点位置，然后 j 进行扫描。

j 停在空格分界的位置上，输出两位置之间的字符串

把指针 i 移动在 j 上。

模板应用

#include <iostream>#include <string.h>
using namespace std;
int main(){    char str[1000];        gets(str);        int n = strlen(str);        for(int i = 0; i< n; i++)    {        int j = i;        while(j < n && str[j] != ' ')j ++;                //具体逻辑        for(int k = i; k < j;k++)cout << str[k];                i = j;    }    return 0;}

最长连续不重复子序列

给定一个长度为 nn 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 nn。

第二行包含 nn 个整数（均在 0∼1050∼105 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

1≤n≤1051≤n≤105

输入样例：

51 2 2 3 5

输出样例：

3

朴素做法：

for(int i = 0; i < n; i ++){  for(int j = 0; j < i; j++)       if(chack(i,j))       {           res = max(res, i - j +1);       }}

双指针算法模板：

for(int i = 0; i < n; i++){    while(j <= i && check(j,i))j ++;    res = max(res, i - j + 1);}

双指针基本思路：

首先 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 可以不写。

for(int i = 0; i < n; i++){    while(S[a[i]] > 1)XXX;    res = max(res, i - j + 1);}

代码

#include <iostream>
using namespace std;
const int N = 100010;
int S[N],a[N];int n;

int main(){    cin >> n;    for(int i = 0; i< n; i++)cin >> a[i];        int res = 0;    for(int i = 0, j = 0; i < n; i++)    {        S[a[i]]++;        while(S[a[i]] > 1)        {            //当停止时，说明和i相同的值已经被删了，即j停在了重复值之后            S[a[j]] --;            j ++;        }                res = max(res, i - j + 1);    }    cout << res;    return 0;}

当数组很大的时候，可以考虑采用哈希表来实现。哈希表可以存任意量，包括字母，数字，字符串。

注意：要想采用双指针算法优化，重要的是这一种单调关系。