简单介绍

概念：two pointers广义上概念就是利用问题本身与序列的特性，利用下标i、j对序列进行扫描，以较低的复杂度来解决问题，其实也不太像是一种算法，说来可以看做是一种编程技巧，一种思想比较适合。

例如在一个递增序列中找到a+b=c的数然后输出a，b的值，M是我们自己指定的数，常规做法很容易想到，两个下标遍历序列做个二重循环就可以解决问题，时间复杂度为o(n^2)。

高复杂度的原因:
（1）对于一个确定的a[i]来说，若当前的a[j]满足a[i]+a[j]>M，显然也有a[i]+a[j+1]>M成立（序列递增），因此不需要对a[j]后进行枚举。如果无视，会造成j的无效枚举。
（2）对于某个a[i]来说，若当前的a[j]满足a[i]+a[j]>M，显然也有a[i+1]+a[j]>M成立（序列递增），因此不需要对a[j]后进行枚举。

但是这个方法是比较烂的，当序列数字较多时（在10^5规模时已经不可承受）时间复杂度会非常的高，程序可行性大打折扣，这时候就要另辟蹊径。

加入现在定义i为A序列首位，j为A序列末位，两下标往中间移动，设计while循环终止条件（i>=j）即可，然后比对是否存在满足条件的i，j然后进行输出。

1. 如果此时已经找到一个A[i]+A[j]=M，想要继续分析找到合适的i和j，下一步应该如何选择才能更加的高效，显然可以从给出的背景条件来看，由A序列是个递增序列可以知道，如果在找到的上述A[i]+A[j]=M条件下将i单独后移显然结果大于c的，而将j前移显然后来的结果都是小于c的，所以下一个查找区间应该[i+1,j-1]开始。

2. 如果找到的A[i]+A[j]>M，因此不等式a[i+1]+a[j]>M成立，显然此时如果将i后移这个结果只会继续增加，偏离了正确的结果，所以下一个查找区间应该只会在[i,j-1]内。

3. 如果找到的A[i]+A[j]<M，因此不等式a[i]+a[j-1]<M成立，显然此时如果将j前移这个结果只会继续减少，偏离了正确的结果，所以下一个查找区间应该只会在[i+1,j]内。

说的有点模糊，但请好好分析下，这个思想应该是不太难的，用此方法实现复杂度显然降低不少，此时复杂度为o(n)，实现的伪代码如下：

    while(i<j)
    {
        if(a[i]+a[j]==c)
        {
            printf("%d %d\n", i,j)
            i++;
            j--;
        }
        else if(a[i]+a[j]<m)
        {
            i++;
        }
        else
        {
            j--;
        }
    }

复杂度为o(n)的原因

i初值为0，j初值为n-1，程序仅有i递增、j递减的操作，因此i和k的操作次数最多为n次，因此时间复杂度为O（n）

two pointers的思想

原始的含义就是解决这样的问题

在一个递增序列中找到a+b=c的数然后输出a，b的值，M是我们自己指定的数

而广义上的two pointers利用问题本身与序列的特性，使用i和j两个下标对序列进行扫描（同向方向都可），以较低复杂度解决问题。

two pointers的应用场景

• 序列合并问题
• 归并排序
• 快速排序

参考

two pointers、归并排序、快速排序问题

版权所有：可定博客 © WNAG.COM.CN

本文标题：《双指针-two pointers》

本文链接：https://wnag.com.cn/902.html

特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：wangyeuuu@qq.com，尊重他人劳动成果，谢过~