Javaで指定された合計になる配列内の数値のすべてのペアを検索します

投稿日: 2019-10-18 2022-10-12
タグ: Algorithms, Java, Java Array

1. 概要

このクイックチュートリアルでは、合計が特定の数値に等しい配列内の数値のすべてのペアを見つけるためのアルゴリズムを実装する方法を示します。 問題への2つのアプローチに焦点を当てます。

最初のアプローチでは、一意性に関係なく、そのようなすべてのペアを見つけます。 2番目では、一意の番号の組み合わせのみを検索し、冗長なペアを削除します。

それぞれのアプローチについて、2つの実装を紹介します。 for ループを使用する従来の実装と、Java 8StreamAPIを使用する2つ目の実装です。

2. 一致するすべてのペアを返す

整数の配列を反復処理し、ブルートを使用して、指定された数（ sum ）に合計されるすべてのペア（iおよびj）を見つけます。強制、ネストされたループアプローチ。 このアルゴリズムの実行時の複雑さはO（n2）になります。

デモンストレーションでは、次の input 配列を使用して、合計が6に等しいすべての数値のペアを探します。

int[] input = { 2, 4, 3, 3 };

このアプローチでは、アルゴリズムは次を返す必要があります。

{2,4}, {4,2}, {3,3}, {3,3}

各アルゴリズムで、合計がターゲット数になるターゲットの数のペアが見つかったら、ユーティリティメソッド addPairs（i、j）を使用してペアを収集します。

ソリューションの実装を考える最初の方法は、従来のforループを使用することです。

for (int i = 0; i < input.length; i++) {
    for (int j = 0; j < input.length; j++) {
        if (j != i && (input[i] + input[j]) == sum) {
            addPairs(input[i], sum-input[i]));
        }
    }
}

これは少し初歩的なことかもしれないので、 Java 8 StreamAPIを使用して実装を作成しましょう。

ここでは、メソッド IntStream.range を使用して、数値のシーケンシャルストリームを生成します。次に、条件でそれらをフィルタリングします。数値1+数値2= sum ：

IntStream.range(0,  input.length)
    .forEach(i -> IntStream.range(0,  input.length)
        .filter(j -> i != j && input[i] + input[j] == sum)
        .forEach(j -> addPairs(input[i], input[j]))
);

3. すべての一意の一致するペアを返します

この例では、冗長なペアを省略して、一意の番号の組み合わせのみを返す、よりスマートなアルゴリズムを開発する必要があります。

これを実現するために、すべての要素を（ソートせずに）ハッシュマップに追加し、最初にペアがすでに表示されているかどうかを確認します。そうでない場合は、取得して表示されているようにマークします（valueフィールドをnullとして設定します）。

したがって、以前と同じ input 配列を使用し、 6 のターゲット合計を使用すると、アルゴリズムは異なる数値の組み合わせのみを返す必要があります。

{2,4}, {3,3}

従来のforループを使用すると、次のようになります。

Map<Integer, Integer> pairs = new HashMap();
for (int i : input) {
    if (pairs.containsKey(i)) {
        if (pairs.get(i) != null) {            
            addPairs(i, sum-i);
        }                
        pairs.put(sum - i, null);
    } else if (!pairs.containsValue(i)) {        
        pairs.put(sum-i, i);
    }
}

forループを1つだけ使用するため、この実装は以前の複雑さを改善することに注意してください。したがって、O（n）が使用されます。

次に、Java8とStreamAPIを使用して問題を解決しましょう。

Map<Integer, Integer> pairs = new HashMap();
IntStream.range(0, input.length).forEach(i -> {
    if (pairs.containsKey(input[i])) {
        if (pairs.get(input[i]) != null) {
            addPairs(input[i], sum - input[i]);
        }
        pairs.put(sum - input[i], null);
    } else if (!pairs.containsValue(input[i])) {
        pairs.put(sum - input[i], input[i]);
    }
});

4. 結論

この記事では、Javaで特定の数を合計するすべてのペアを見つけるためのいくつかの異なる方法について説明しました。それぞれが2つのJavaコアメソッドを使用する2つの異なるソリューションを見ました。

いつものように、この記事に示されているすべてのコードサンプルは GitHub で見つけることができます—これはMavenプロジェクトなので、コンパイルと実行が簡単なはずです。

getdocs

13036