隨筆檔案

兩個指針的作用

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

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

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

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

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

當一個指針無法很好解決問題時，應該再增添一個指針，多一個幫手。