上次我們一起分析了滑動(dòng)窗口這個(gè)常用的算法技巧，使用倆指針即可維護(hù)滿足條件的窗口，我也跟大家說過，雙指針也是算法中重要的工具，很多題目因?yàn)橐肓穗p指針的思想變得異常簡單。
一開始我在做題的時(shí)候，最喜歡用的就是暴力無腦循環(huán)，但是很多時(shí)候得到的算法復(fù)雜度都很高，后來我就發(fā)現(xiàn)一個(gè)規(guī)律，凡是題目說給我們一個(gè)排好序的數(shù)組或者鏈表，要我們從中找到滿足條件的一系列元素時(shí)，往往在提示我們用雙指針解題，這是為什么呢，我們接著往下看。
先看一道題，給定一個(gè)排序好的數(shù)組跟一個(gè)數(shù)字，找出和跟這個(gè)數(shù)字相等的一對(duì)數(shù)字，返回他們的索引。這道題目，我一眼就看出暴力循環(huán)，有木有？！
寫起來賊簡單，這活兒我熟，我來寫：)
public static int[] search(int[] arr, int targetSum) {
for (int i = 0; i < arr.length) {
for (int j = i + 1; j < arr.length; j++) {
if (targetSum - arr[j] == arr[i]) {
return new int[]{i, j};
}
}
}
return new int[]{-1, -1};
}
在這里我們依次迭代剩余元素來尋找符合條件的兩個(gè)數(shù)，由于兩層循環(huán)，時(shí)間復(fù)雜度為O(n^2)。這肯定不是最好的辦法，因?yàn)轭}目給我們的排序好的數(shù)組這個(gè)屬性完全沒有用到，題目肯定不會(huì)給我們無用的信息，我們來看看排序好的數(shù)組有什么不一樣。
對(duì)于排序好的數(shù)組來說，從前往后越來越大，這是一個(gè)很重要的屬性，那我們就可以分別在數(shù)組前后各放置一個(gè)指針，start跟end，指著兩個(gè)數(shù)，然后我們可以做兩件事：
- 如果這兩個(gè)數(shù)之和大于target，那意味著我們需要兩數(shù)之和小一點(diǎn)，那我們就把end往前移動(dòng)。
- 要是糧食之和小于target，那說明我們得把start往后移動(dòng)了。
這就是二分搜索的思想，我們來實(shí)現(xiàn)一下代碼：
public static int[] search(int[] arr, int targetSum) {
int start = 0;
int end = arr.length - 1;
while (start < end) {
if (arr[start] + arr[end] == targetSum) {
return new int[]{start, end};
}
if (arr[start] + arr[end] > targetSum) {
end--;
} else {
start++;
}
}
return new int[]{-1, -1};
}
核心思想就是這么簡單，用倆指針在排序好的數(shù)組里快速迭代，但是雙指針的絕不僅僅是用來二分搜索，我們?cè)賮砜匆坏李}。
給定一個(gè)排序好的數(shù)組，去掉重復(fù)元素，返回去重后的新長度，不準(zhǔn)用額外的空間。也就是說，如果這個(gè)數(shù)組是
[2, 3, 3, 3, 6, 9, 9]
這個(gè)情況下我們得返回4，而且不能使用額外的數(shù)據(jù)結(jié)果來幫助去重。乍一看不用額外空間似乎沒法做，這可咋整，那我們只能在原數(shù)組上進(jìn)行修改了。但是好在這個(gè)數(shù)組是排序好的，那也就是說，重復(fù)元素都是相鄰的，但數(shù)組不像List一樣可以直接刪掉某個(gè)元素，我們只能想辦法把數(shù)組中，重復(fù)的元素扔到一邊。
那其實(shí)我們這里就可以使用兩個(gè)指針，一個(gè)指著下一個(gè)非重復(fù)元素應(yīng)該放置的位置，一個(gè)迭代整個(gè)數(shù)組尋找下一個(gè)非重復(fù)元素的位置，這么說可能比較拗口，我們直接來看代碼就能理解了：
public static int remove(int[] arr) {
int nextNonDuplicate = 0; // 記錄放置非重復(fù)元素的位置
for (int i = 1; i < arr.length; i++) {
if (arr[nextNonDuplicate] != arr[i]) {
arr[nextNonDuplicate + 1] = arr[i];
nextNonDuplicate++;
}
}
return nextNonDuplicate + 1;
}
我們不管數(shù)組里有多少個(gè)重復(fù)元素，在也不管哪里有重復(fù)元素，還拿[2, 3, 3, 3, 6, 9, 9]這個(gè)數(shù)組來說，去重是去掉后面出現(xiàn)的一樣的元素，nextNonDuplicate 指向索引0，它肯定是第一次出現(xiàn)的，i指向位置為1的元素，然后判斷nextNonDuplicate 位置的元素(即2)跟i指向的元素(即3)是否相等，當(dāng)然不等，那i指向的元素放在nextNonDuplicate后面就不重復(fù)，那nextNonDuplicate+1 就該設(shè)置為i指向的元素(即3)(其實(shí)本來也就是3)，但是在接著往下迭代，nextNonDuplicate 還指向索引為1的位置，而i繼續(xù)尋找下一個(gè)不重復(fù)元素的索引，已經(jīng)到了索引為3的位置,(因?yàn)?code>nextNonDuplicate跟i指向的元素在這期間一直相等)，直到i=4，再次出現(xiàn)不等的情況，我們給nextNonDuplicate+1所指的位置賦新值。，因?yàn)?code>i>=nextNonDuplicate，我們不會(huì)漏掉任何元素，這樣我們就能保證nextNonDuplicate指向的值，一定是第一次出現(xiàn)的元素。到最后結(jié)束，所有第一次出現(xiàn)的元素都被移動(dòng)到了數(shù)組的左邊，nextNonDuplicate指示的位置一定是當(dāng)前最遠(yuǎn)的無重復(fù)元素的索引。
這兩個(gè)例子應(yīng)該能促使大家對(duì)雙指針的技巧有所思考，大家千萬要記住凡是題目中出現(xiàn)排序好的數(shù)組等字眼的，都可以試著用雙指針去解決。
