2

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

 1 year ago
source link: https://blog.51cto.com/u_15736437/5765085
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

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

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

双指针算法

双指针算法的常见情况：

  • 双指针在两个数组上（例如归并排序等等）
算法基础（六）| 双指针算法及模板应用_算法_02
双指针在一个数组上
算法基础（六）| 双指针算法及模板应用_算法_03

常见通用代码模板

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



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



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



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



举例：分行输出字符串



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



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



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



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



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



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



把指针i移动在j上。



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



#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



输入样例：



5
1 2 2 3 5



输出样例：



朴素做法：



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如果前移，那么就证明刚刚最大的位置并非最优值，这与刚刚的结论矛盾。
算法基础（六）| 双指针算法及模板应用_算法_07



有了单调这一层性质，就可以采用双指针这种单调队列的思想优化。因为可以使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;
}



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



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

        

        

            

                report
            

        

    







        
Recommend

        



                

    
About Joyk

    
 





Aggregate valuable and interesting links.

Joyk means Joy of geeK