O [n^2]で3つの配列で結果A [i] + B [j] = C [k]を与えるすべての組み合わせを見つける

Question

3つの配列があり、各配列のサイズはNです。 O [n^2]にのみA[i]+B[j]=C[k]となる組み合わせを見つける。

Answer 1

更新：質問は後でJavaで実装するように特に修正されました。 Pythonのアルゴリズムと説明は有効なままですが、以下のJava実装も追加しました。

---

（平均）時間計算O(1)とCに存在するかどうかをテストするためにhashmap（またはセット）を使用。それから、すべてのペアを反復する必要があります。(a,b) | a <- A, b <- B、合計時間複雑度はO(n^2)です。例えば

、Pythonの であなたは、このようにそれを行うことができます：

c = set(C) 
for a in A: 
    for b in B: 
     if a + b in c: 
      print a, b, a + b 

クイックテスト：

>>> A = [1,2,3] 
>>> B = [3,4,5] 
>>> C = [1,4,7] 
>>> c = set(C) 
>>> for a in A: 
...  for b in B: 
...   if a + b in c: 
...    print a, b, a + b 
... 
1 3 4 
2 5 7 
3 4 7 

あるいは、リスト内包と短いバージョン：

>>> c = set(C) 
>>> [(a,b,a+b) for a in A for b in B if a+b in c] 
[(1, 3, 4), (2, 5, 7), (3, 4, 7)] 

---

Javaの実装は基本的に同じです。

import java.util.HashSet; 

class Pairs { 
    public static void main(String[] args) { 
     Integer[] A = new Integer[]{1,2,3}; 
     Integer[] B = new Integer[]{3,4,5}; 
     Integer[] C = new Integer[]{1,4,7}; 

     HashSet<Integer> c = new HashSet<Integer>(); 
     for (int i = 0; i < C.length; i++) { 
      c.add(C[i]); 
     } 

     for (int i = 0; i < A.length; i++) { 
      for (int j = 0; j < B.length; j++) { 
       if (c.contains(A[i] + B[j])) { 
        System.out.format("%d %d %d%n", A[i], B[j], A[i]+B[j]); 
       } 
      } 
     } 
    } 
} 

Answer 2

単純な問題があります：指定された二つの配列及び数は合計を与えるアレイからのすべての組み合わせを見つけることが=番号をキー観察和A[i]+B[j]がアレイCに存在するかどうかをチェックするためのjava.util.HashSetを使用することです。これはO（n）で解くことができます。

私たちは、大きい方のためのソリューションの一部として、そのソリューションを使用することができます。

（私はすべての要素が異なっていることを仮定している - それは物事ビットを簡素化します）あなたを行う

sort(A) 
sort(B) 
sort(C) 
for(int indexC=0;indexC<N;++indexC) 
    int indexA=0 
    int indexB=N-1 
    while(indexA<0) 
     //find all combinations in A,B with sum=C[indexC] 
     int sum=A[indexA]+B[indexB] 
     if(sum==C[indexC]) 
      OutputCombination(indexA,indexB,indexC) 
     if(sum<C[indexC]) 
      ++indexA 
     else if(sum>C[indexC]) 
      --indexB 
     else 
      ++indexA 
      --indexB