two pointers

时间:2022-03-16 05:47:59

  two pointers是算法编程中一种非常重要的思想,但是很少会有教材单独拿出来将,其中一个原因是它更倾向于是一种编程技巧,而长得不太像是一个是“算法”的模样。two pointers的思想十分简介,但却提供了非常高的算法效率。

  以一个例子引入:给定一个递增的正整数序列和一个正整数M,求序列中的连个个不同位置的数a和b,使得它们的和恰好为M,输出所有满足条件的方案。例如给定序列{1,2,3,4,5,6}和正整数M=8,就存在2+6=8和3+5=8成立。

  本题的一个最直观的想法是:暴力求解,使用二重循环枚举序列中的整数a和b,判断它们的和是不是M,如果是,输出方案,如果不是,则继续枚举。代码如下:

for(int i = ;i < n; i ++){
for(int j = i+; j < n; j++){
if(a[i]+a[j]==M){
cout<<a[i]<<" "<<a[j]<<endl;
}
}
}

  显然,这样做的时间复杂度是O(n^2),对n在10^5的规模时是不可承受的。

  那么根据two pointers的思想,代码如下:

  

while(i<j){
if(a[i]+a[j]==M){
cout<<a[i]<<" "<<a[j]<<endl;
i++;
j--;
}else if(a[i]+a[j]<M){
i++;
}else{
j--;
}
}

 明显,此方法的时间复杂度为O(n),可以发现,two poin的思想慧聪分利用了递增序列的性质,以很浅显的思想降低了复杂度。