一個含有多個元素的數組，有多種排序方式。它可以升序排列，可以降序排列，也可以像我們以前章節說過的，以波浪形方式排序，現在我們要看到的一種是絕對值排序。對于數組A,絕對值排序滿足以下條件：|A[i]| < |A[j]|，只要i < j。例如下面的數組就是絕對值排序：

A:-49, 75, 103, -147, 164,-197,-238,314,348,-422

• 1

給定一個整數k，請你從數組中找出兩個元素下標i,j，使得A[i]+A[j] == k。如果不存在這樣的元素配對，你返回(-1,-1)。

對于這個題目，我們曾經討論過當數組元素全是整數時的情況，要找到滿足條件的配對(i,j)，我們讓i從0開始，然后計算m = k - A[i]，接著在(i+1, n)這部分元素中，使用折半查找，看看有沒有元素正好等于m，如果在(i+1,n)中存在下標j，滿足A[j] == m 那么我們就可以直接返回配對(i,j)，這種做法在數組元素全是正數，全是負數，以及是絕對值排序時都成立，只是在絕對值排序的數組中，進行二分查找時，需要比對的是元素的絕對值。使用這種查找辦法，算法的時間復雜度是O(n*lg(n))。

上面算法形式很緊湊，無論數組全是正數，負數，還是絕對值排序時，都有效。但我們還可以找到效率更高的算法，假設數組中的元素全是同一符號，也就是全是正數，或全是負數時，要找到A[i]+A[j] == k，我們可以這么做：?
1，讓i = 0, j = n-1, 如果A[i] + A[j] == k 那么算法結束。?
2，如果A[i] + A[j] < k, 那么令 i = i +1;?
3，如果A[i] + A[j] > k, 那么令 j = j -1;?
上面步驟一直運行到i == j，或是A[i]+A[j] == k為止。這種做法的時間復雜度是O(n)。其算法效率比前面提到的方法要好，但問題在于，這種做法不能運用于絕對值排序的數組。為了能夠應對絕對值排序的數組，我們需要對算法做一些改進。

對于滿足A[i]+A[j] == k的元素，它必定滿足下面三種情況之一：?
1，A[i]和A[j]都是正數。?
2，A[i]和A[j]都是負數。?
3，A[i]和A[j]是一正一負。?
對于前兩種情況我們可以直接使用剛才使用的方法，對于第三種情況，我們需要做一個調整，對于第三種情況，我們讓i指向最后一個整數，讓j指向最后一個負數，如果A[i]+A[j] == k，那么算法結束，如果A[i]+A[j] > k, 那么讓i指向下一個正數，如果A[i]+A[j] < k，那么讓j指向下一個負數。

因此在查找滿足條件的元素配對時，我們先看看前兩種情況是否能查找到滿足條件的元素，如果不行，那么我們再依據第三種情況去查找，無論是否存在滿足條件的元素配對，我們算法的時間復雜度都是O(n)。我們看看相應的代碼實現：

public class FindPairInAbsoluteSortedArray {private int[] sortedArray;private int indexI;private int indexJ;private boolean bSuccessed = false;private int k ;public FindPairInAbsoluteSortedArray(int[] sortedArray, int k) {this.sortedArray = sortedArray;this.indexI = -1;this.indexJ = -1;this.k = k;}private void findPairWithSameSign(boolean positive) {/** 如果滿足條件的元素對都是正數或負數的話，那么用i指向第一個正數或負數，j指向最后一個整數或負數，* 如果兩元素都是正數，如果A[i]+A[j] == k，算法結束，如果A[i] + A[j] > k, 那么j--；* 如果A[i]+A[j] < k，那么i++ * * 如果兩元素都是負數，A[i] + A[j] == k 算法結束，如果A[i]+A[j]>k, 那么i++,直到下一個負數* 如果A[i]+A[j] < k ，那么j-- 直到下一個負數*/int i = 0, j = this.sortedArray.length - 1;if (positive == true) {while (this.sortedArray[i] < 0) {i++;}while (this.sortedArray[j] < 0) {j--;}} else {while (this.sortedArray[i] > 0) {i++;}while (this.sortedArray[j] > 0) {j--;}}do {if (this.sortedArray[i] + this.sortedArray[j] == this.k) {this.bSuccessed = true;this.indexI = i;this.indexJ = j;break;}if (this.sortedArray[i] + this.sortedArray[j] < this.k) {if (positive == true) {i++;while (i < this.sortedArray.length && this.sortedArray[i] < 0) {i++;}} else {j--;while (j > 0 && this.sortedArray[j] > 0) {j--;}}}else {if (positive == true) {j--;while (i < this.sortedArray.length && this.sortedArray[j] < 0) {j--;}} else {i++;while (i < this.sortedArray.length && this.sortedArray[i] > 0) {i++;}}}}while (i < j);}private void findPairWithDifferentSign() {/** 把i指向最后一個正數，把j指向最后一個負數，如果A[i] + A[j] == k, 算法結束* 如果A[i] + A[j] < k，那么j--;* 如果A[i] + A[j] > k , 那么k--*/int i = this.sortedArray.length-1;int j = this.sortedArray.length-1;while (this.sortedArray[i] < 0 && i > 0) {i--;}while (this.sortedArray[j] > 0 && j > 0) {j--;}do {if (this.sortedArray[i] + this.sortedArray[j] == this.k) {this.indexI = i;this.indexJ = j;this.bSuccessed = true;break;}if (this.sortedArray[i] + this.sortedArray[j] > k) {i--;while (i > 0 && this.sortedArray[i] < 0) {i--;}} else {j--;while (j > 0 && this.sortedArray[j] > 0) {j--;}}}while(i > 0 && j > 0);}public void findPair() {this.findPairWithSameSign(true);if (this.bSuccessed == false) {this.findPairWithSameSign(false);}if (this.bSuccessed == false) {this.findPairWithDifferentSign();}if (this.bSuccessed == false) {System.out.println("No such pair exist in  array");} else {System.out.println("The index are " + this.indexI + " and " + this.indexJ + " with value of " + this.sortedArray[this.indexI] + " and " + this.sortedArray[this.indexJ]);}}
}

類FindPairInAbsoluteSortedArray用于在絕對值排序的數組中查找滿足條件的元素配對，它先根據兩元素都是正數的情況下查找，然后再根據兩元素都是負數的情況下查找，如果這兩種情況都找不到，再嘗試兩元素一正一負的情況下查找，如果三種情況都找不到滿足條件的元素，那么這樣的元素在數組中不存在。

我們看看入口代碼：

public class Searching {public static void main(String[] args) {int[] A = {-49, 75, 103, -147, 164, -197, -238, 314, 348, -422};int k = 167;FindPairInAbsoluteSortedArray fi = new FindPairInAbsoluteSortedArray(A, k);fi.findPair();}
}

上面代碼運行結果如下：?

從運行結果上看，我們算法的實現是正確的，并且這種做法比原先依靠折半查找的效率要高，它的算法復雜度為O(n)，空間復雜度為O(1)。