並べ替えられていない配列の値を見つける

Question

配列内の任意の2つの数値の合計のすべての組み合わせを調べる必要があります。等しい場合は印刷します。 この問題に対する線形解法は、O（N^2）の複雑さを有する。 ソートしてからバイナリ比較をすることを考えました。複雑さはまだ（NlogN + N）

私はそれのすべての組み合わせを見つける必要があります。

この問題の線形解法 例：

//Linear search, find all the combinations 
Find(int a[], int Target) 
    { 
     for(i=0; i<arr_size; i++) 
      for(j=0; j<arr_size; j++) 
       if((a[i]+a[j]) == Target) 
        cout<<a[i]<<a[j] 
    } 

さらに複雑さを減らす方法はありますか？

おかげで、あなたが最初にすべての不可能をフィルタリングすることができ 達人

Answer 1

。これはアレイを通して2回の反復しか必要とせず、セットを劇的に減少させる可能性がある。そうでない場合は、2回の繰り返ししか失われません。

まず、最小の数字を見つけて、すべての値>（目標 - 最小数）を除外します。

Answer 2

は少しパフォーマンス

private static void find(int[] a, int target) { 

    for (int i = 0; i < a.length; i++) { 
     if (a[i] == target) { 
      System.out.println("result found"); 
      break; 
     } 
     if (a[i] > target) { 
      break; 
     } 
     for (int j = 0; j < a.length; j++) { 
      if ((i != j && (a[i] + a[j]) == target)) { 
       System.out.println("result found"); 
      } 
     } 
    } 
}