two pointers

　　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的思想慧聪分利用了递增序列的性质，以很浅显的思想降低了复杂度。

巴特西

two pointers

最新文章

热门文章