隨筆檔案

兩個指針的作用

兩個指針一般用在一個序列中。
在一個序列中處理問題時，如果只使用一個指針，可能會造成雙重循環(huán)的問題，結(jié)果時間復(fù)雜度會是 O(N) 。
如果采用兩個指針可以很好地解決問題，時間復(fù)雜度也可以得到改進(jìn)。

采用兩個指針的例子很多，這里舉幾個：
1.
自動文摘中，如果采用循環(huán)查找的方法，時間復(fù)雜度是冪次方。采用兩個指針，分別指向文摘的開始處和結(jié)束處可以在 O(N) 的時間復(fù)雜度內(nèi)找到文摘。

2.
求連續(xù)數(shù)字之和等于一給定數(shù)，例如給定數(shù)是 15 ，則結(jié)果有 1 2 3 4 5、4 5 6、7 8 三種結(jié)果。
如果采用循環(huán)的方法事件復(fù)雜度是 O(N^2)
可以采用兩個指針，分別指向 small 和 big 。當(dāng) sum(small ... big) 大于給定數(shù)時，small 指針右移，當(dāng) sum 小于給定數(shù)時，big 指針右移。直到 small 是給定數(shù)的一半時。

3.
調(diào)整數(shù)組，是前半部分是某種類型的數(shù)，后半部分是某種類型的數(shù)。
比如前半部分是奇數(shù)，后半部分是偶數(shù)
前半部分是負(fù)數(shù)，后半部分是非負(fù)數(shù)
采用兩個指針，分別從左右兩端進(jìn)行掃描，檢測，如果符合條件則交換兩數(shù)，直到兩個指針交叉為止。

4.
求一個數(shù)組中兩個數(shù)的和等于一定數(shù)。
先對數(shù)組排序
然后從數(shù)組兩端用兩個指針掃描，檢測，直到兩個指針交叉為止。

當(dāng)一個指針無法很好解決問題時，應(yīng)該再增添一個指針，多一個幫手。