双指针-two pointers
简单介绍
概念：two pointers广义上概念就是利用问题本身与序列的特性，利用下标i、j对序列进行扫描，以较低的复杂度来解决问题，其实也不太像是一种算法，说来可以看做是一种编程技巧，一种思想比较适合。
例如在一个递增序列中找到a+b=c的数然后输出a，b的值，M是我们自己指定的数，常规做法很容易想到，两个下标遍历序列做个二重循环就可以解决问题，时间复杂度为o(n^2)。
高复杂度的原因: （1）对于一个确定的ai来说，若当前的aj满足ai+aj>M，显然也有ai+aj+1>M成立（序列递增），因此不需要对aj后进行枚举。如果无视，会造成j的无效枚举。 （2）对于某个ai来说，若当前的aj满足ai+aj>M，显然也有ai+1+aj>M成立（序列递增），因此不需要对aj后进行枚举。
但是这个方法是比较烂的，当序列数字较多时（在10^5规模时已经不可承受）时间复杂度会非常的高，程序可行性大打折扣，这时候就要另辟蹊径。
加入现在定义i为A序列首位，j为A序列末位，两下标往中间移动，设计while循环终止条件（i>=j）即可，然后比对是否存在满足条件的i，j然后进行输出。
- 如果此时已经找到一个Ai+Aj=M，想要继续分析找到合适的i和j，下一步应该如何选择才能更加的高效，显然可以从给出的背景条件来看，由A序列是个递增序列可以知道，如果在找到的上述Ai+Aj=M条件下将i单独后移显然结果大于c的，而将j前移显然后来的结果都是小于c的，所以下一个查找区间应该i+1,j-1开始。
- 如果找到的
A[i]+A[j]>M，因此不等式ai+1+aj>M成立，显然此时如果将i后移这个结果只会继续增加，偏离了正确的结果，所以下一个查找区间应该只会在i,j-1内。 - 如果找到的
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的应用场景
- 序列合并问题
- 归并排序
- 快速排序
参考
版权所有：可定博客 © WNAG.COM.CN
本文标题：《双指针-two pointers》
本文链接：https://cloud.tencent.com/developer/article/1616938
特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：wangyeuuu@qq.com，尊重他人劳动成果，谢过~