バイナリ検索が失敗した場合の検索

Question

私は本当に興味深いプログラミング課題を解決しようとしています。ここにある：

書き込みリストとターゲット合計与えられ、合計 目標合計に等しい任意の二つの異なる要素の ゼロベースのインデックスを返す関数。そのような要素がない場合、関数は を返します。 例えば、findTwoSum（新しいINT [] {1、3、5、7、9}、12）インデックスの次のタプルのいずれかを返さなければならない：

1, 4 (3 + 9 = 12) 
2, 3 (5 + 7 = 12) 
3, 2 (7 + 5 = 12) 
4, 1 (9 + 3 = 12) 

は、単純な右であるべきか？だからここに私の機能があります：

public static int[] findTwoSum(int[] list, int sum) { 
     int[] indices = null; 
     for(int i = 0; i < list.length; i++) { 
      int currentNum = list[i]; 
      int findNum = sum - currentNum; 
      int length = list.length; 
      int min = i; 
      int max = length-1; 

      while(max >= min) { 
       int guess = (max+min)/2; 

       if(list[guess] == findNum) { 
        return new int[] {i,guess}; 
       } 

       if(list[guess] < findNum) { 
        min = guess + 1; 
       } 

       if(list[guess] > findNum) { 
        max = guess - 1; 
       } 
      } 

     } 


     return indices; 
    } 

コードは、非常に単純である、配列内のすべての要素のために、それは彼らの合計が提供sumに等しくなるように、バイナリ検索、別の要素を使用して検索しようとします。私はこのコードをテストしたところ、提供された配列がソートされていると仮定して、失敗したシナリオを見つけることができませんでした。しかし、TestDomeでこのコードを実行すると、最後のケースが失敗し、何とか間違った解決策になります。誰もこのアプローチで何が間違っているかを指摘できますか？

Answer 1

コードは、リストがソートされていることを前提としています。問題文は要素の順序について何も言わないので、配列を自分でソートする必要があります。インデックスが必要なので、値とインデックスのペアをソートする必要があります。

より速いアプローチは、カウントと元のインデックスを含むハッシュマップにデータを置き、リスト内の各nの存在がTarget - nであるかどうかをチェックすることです。 Targetが2*nに等しい場合、特殊ケースのカウントが必要です。

Answer 2

初期リストのソートされた順序に関する質問と明確化に基づいて、最初のリストはソートされていないようです。したがって、リストをソートする必要があり、元のインデックスを別のリストに別々に格納する必要があります。

配列をソートして元のインデックスを書き留めた後、arr[]にソートされたリストが含まれ、indices[]に対応する要素の元のインデックスがarr[]であるとします。簡単な言葉では、indices[i]は、要素の元のインデックスを返しますarr[i]。

今、あなたはペアを見つけるための2-SUMアルゴリズムに従うことができます：

• 初期ソートされた配列に候補 要素を見つけるための2つのインデックス変数を。最初の左端のインデックス

  • 初期化：L < RながらR = ar_size-1

• ループL = 0

• は、右から2番目のインデックスを初期化します。

  • 場合、戻り対（指数[L]、インデックス[R]）（[L] + ARR [R] ==和ARR）エルス
  • IF（ARR [L] + ARR [R] NULL

  あなたはまた、代わりに2-SUM手順のバイナリ検索技術を使用することができます返さない - 全体のアレイ内の候補者が他のr--の

<合計）、その後リットル++。

希望すると助かります！

Answer 3

このソリューションをお試しください。配列をソートし、バイナリ検索を使用して2番目の要素を探します。sum -nでなければなりません。

一致するペアが見つかった場合、元のインデックスを決定するために、元の配列内で検索されます。

public static int[] findTwoSum(int[] list, int sum) { 
    int len = list.length; 
    int[] sortedList= Arrays.copyOf(list, len); 
    Arrays.sort(sortedList); 
    for (int i = 0; i < len; i++) { 
     int m = list[i]; 
     int j = Arrays.binarySearch(sortedList, sum - m); 
     if (j >= 0 && i != j) 
      return new int[] { i, findIndex(list, sortedList[j]) }; 
    } 
    return null; 
} 

public static int findIndex(int[] list, int m) { 
    int len = list.length; 
    for (int i = 0; i < len; i++) { 
     if (list[i] == m) 
      return i; 
    } 
    return -1; 
}