バイナリ検索を使用したトリプレット和

Question

トリプレットの合計を見つけるためのさまざまなアプローチを考えていましたが、これを見つけたのはfinding a triplet having a given sumです。だから私はそれを試してみることを考えた。

My algorithm: 
1) Sort the numbers //O(nlogn) 
2) Initialize low=0 and high=size-1 
3) loop till low<high 
    a) if sum-arr[high]-arr[low]< 0 , then decrement high 
    b) if third number is not in range of (low,high) then break the loop 
    c) else search for third number using binary search 

しかし、正しい出力が得られません。私のロジックはどこが間違っているのか分かりません。なぜなら、かなり簡単なバイナリ検索です。以下は私が実装したものです。 私のミスは私が知っている

static boolean isTriplet(int a[], int size, int sum) 
    { 
     Arrays.sort(a); //sort the numbers 

     int low = 0; 
     int high = size-1; 
     while(low<high) 
     { 

      int third = sum - a[high] - a[low]; 
      if(third<0) 
       high--; 
      else if(!(sum - a[high] - a[low]>a[low] && sum - a[high] - a[low]< a[high])) //if the number is not within the range then no need to find the index 
       break; 
      else 
      { 
       int index = binarySearch(a,low+1,high-1,third); 
       if(index != -1) 
       { 
        System.out.println(a[low]+" "+a[index]+" "+a[high]); 
        return true; 
       } 
       else 
       low++;     

      } 

     } 
     return false; 
    } 

を聞かせてください、私は入力{1,2,3,4,5,6}と合計= 6でそれを試してみましたが、それはfalseを返し、入力が{3,4,8,1,2,7,5}との和= 20だったとき、私は部分的にあなたの考えを理解

Answer 1

それはtrueを返し完全ではありません。 O（n log（n））時間の複雑さで問題を解決しようとしているようで、可能であるとは確信していません。私はあなたがこれを行うことを決定する方法がわからない：

  else 
      low++; 

私はいくつかのケースでは多分あなたはそこ

high-- 

を行う必要があることを疑います。また、私はこのコードについてはわかりません：

if(third<0) 
    high--; 

3番目> 0の場合はどうなりますか？

私はもう一つの質問を読んで、それはO（n^2 logn）解を提案するので、私はここでそのような解を（Javaで）提供しました。

アイデアは：すべての要素のペアを介して2つのネストされたループ（i、j）を反復し、残りの配列の三つ組を補完する3番目の要素を検索します（その検索はバイナリ検索を使用して行われます）。 。。 - whileループ

public class TripletSum { 
    static boolean solve(int[] a, int k) { 
     Arrays.sort(a); 
     int n = a.length; 

     for(int i = 0; i < n; i++) { 
      for(int j = i + 1; j < n; j++) { 
       int low = j + 1, high = n - 1; 

       while(low <= high) { 
        int middle = (low + high)/2; 
        int sum = a[middle] + a[i] + a[j]; 
        if(sum == k) { 
         return true; 
        } 
        if(sum > k) { 
         high = middle - 1; 
        } 
        if(sum < k) { 
         low = middle + 1; 
        } 
       } 

      } 
     } 

     return false; 
    } 

    public static void main(String[] args) { 
     int[] a = {1,2,3,4,5,6}; 

     System.out.println(solve(a, 20)); 
    } 
} 

EDIT：。 私はいくつかの研究を行なったし、この問題のためのO（N logN個）解決策を見つけることができませんでしたが、この問題は3SUMとして人気があるが判明あなたはWiki page上で見ることができます