与えられた整数の配列を効果的に使用するK相補の組

Question

私はプログラミングがとても新しいです。与えられた整数の配列を効果的に使ってK相補対を見つける必要があります。私は以下のコードを書いています。これには複製が含まれます。私はその重複を排除する必要があります。だから私はその複製を削除し、それを行うためのより効率的な方法があるかどうかを提案してください助けてください。

public class KComplexityOfArray { 


public static StringBuffer oldFunction(int arr[], int k) { 
    int result = 0; 
    StringBuffer sb = new StringBuffer(); 

    for (int i = 0; i < arr.length; i++) { 
     for (int j = 0; j < arr.length; j++) { 
      if (i != j && arr[i] + arr[j] == k) { 
       sb.append(arr[i] + "," + arr[j]); 
       result++; 
      } 
     } 
    } 
    System.out.println(result); 
    return sb; 
} 



public static void main(String[] args) { 
    int[] intArray1 = new int[]{4, 5, 6, 3, 1, 8, -7, -6, 7}; 
    int[] intArray2 = new int[]{1, 2, 7, 5, 6, 3}; 
    int[] intArray = new int[]{4, 5, 6, 3, 1, 8, -7, -6}; 
    int k = 9; 
    System.out.println("No of k complementary pairs : " + oldFunction(intArray2, k)); 
} 

}

は誰がこれを整理するために私を助けてください。おかげ

Answer 1

と

for (int j = 0; j < arr.length; j++) { 

を交換する必要があります。このコードは、2つの異なる要素が対をなす考えると、間違っている：

for (int i = 0; i < arr.length; i++) { 
    for (int j = 0; j < arr.length; j++) { 

代わりに、j=i+1を実行してください。

for (int i = 0; i < arr.length; i++) { 
    for (int j = i+1; j < arr.length; j++) { 

より効率的な方法があるかどうかをご確認ください。

解決策のTCはO(N^2)です。代わりにO(NlogN)に減らすことができます。方法を参照してください。

1. アレイを並べ替えます。
2. iとjの2つのインデックス位置を0とN-1 respに設定します。
3. a[i]とa[j]の合計がkの場合は、それを印刷してください。それ以外の場合、sum < Kの場合はiを1に、それ以外の場合はjを1に減らしてください。 (i < j)

まで

ステップ3を繰り返し

ステップ1 O(NlogN)を取り、残りのステップは、O(N)を取ります。両方を組み合わせると、

Answer 2

は私が正しくあなたの問題を理解していれば、あなたは

for (int j = i+1; j < arr.length; j++) {