找到排序數組的索引，使得a [i] + a [j] = x

Question

這是一個訪問問題：給定integer x和sorted array a[] of N distinct integers，設計linear-time algorithm以確定是否存在兩個不同的索引i和j， a[i] + a[j] == x。不允許輔助存儲。 我已在Java中執行此操作。但我目前的運行時間爲O(nlogn)，因爲我在each iteration上做了binarySearch。所以它不是嚴格的linear。我想知道這個問題是否存在linear time solution。如果是這樣，一些指示可能會有所幫助。

謝謝。

public class SumArrayIndex { 

    public static void main(String[] args){ 

     int[] arr={1,2,3,4,5,6,7,8,9,10}; 
     sumSortedArray(arr, 4); 
     System.out.println(); 
     sumSortedArray(arr, 19); 
     System.out.println(); 
     sumSortedArray(arr, 100); 

    } 

    public static void sumSortedArray(int[] arr, int sum){ 
     for (int i=0;i<arr.length;i++){ 
      int temp=Arrays.binarySearch(arr, sum-arr[i]); 
      if (temp>0 && temp!=i){ 
       System.out.printf("The two indices are %s and %s%n ",i,temp); 
       return; 
      } 
     } 
     System.out.printf("The sum:%s cannot be formed with given array:%s",sum,Arrays.toString(arr)); 
    } 
} 

Answer 1

如所建議的通過在註釋@leif，從array的開始和結束開始，移動開始索引或結束索引如果該總和更大或更小。你應該找到一個開始和結束index，使它們的值等於sum。如果不是這樣，你就不存在這樣的指數。下面這行內容。我沒有測試此代碼，並假設正整數

下面的代碼是自我解釋：

public static void sumSortedArray2(int[] arr, int sum){ 
     boolean found=false; 
     int max=arr.length-1; 
     int min=0; 
     while (min<max){ 
      if(arr[min]+arr[max]<sum) 
       min++; 
      else if (arr[min]+arr[max]>sum) 
       max--; 
      else { 
       found =true; 
       break; 
      } 
    } 
    if (found){ 
     System.out.printf("The two indices are %s and %s%n ",min,max); 
    } 
    else { 
     System.out.printf("The sum:%s cannot be formed with given array:%s",sum,Arrays.toString(arr)); 
    } 
} 

Answer 2

您可以修改你的算法是線性時間，與這些觀察：

1. 不失一般性，你可以說i和j是這樣的arr[i]<arr[j]。證明：如果情況並非如此，則可以交換i和j。
2. 考慮到您在開始時開始搜索，當您搜索sum-arr[i]時，您始終可以搜索索引i的右側;如果sum-arr[i] < arr[i]，你知道，沒有答案，因爲j將的i
3. 左如果您之前的sum-arr[i]搜索已經索引k而不屈服的結果結束了，你的下一個搜索可以索引i和k之間去。
4. 您無需使用二分查找搜索sum-arr[i]：您可以從後面進行線性搜索，並保留點k，其中arr[k] < sum-arr[i]爲您的下一個起點。

這可以讓您建立一個算法來檢查每個項目一次。