概念: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然后进行输出。
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--;
}
}
i初值为0,j初值为n-1,程序仅有i递增、j递减的操作,因此i和k的操作次数最多为n次,因此时间复杂度为O(n)
原始的含义就是解决这样的问题
在一个递增序列中找到a+b=c的数然后输出a,b的值,M是我们自己指定的数
而广义上的two pointers利用问题本身与序列的特性,使用i和j两个下标对序列进行扫描(同向方向都可),以较低复杂度解决问题。
版权所有:可定博客 © WNAG.COM.CN
本文标题:《双指针-two pointers》
本文链接:https://cloud.tencent.com/developer/article/1616938
特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~