与えられた合計になる配列内のすべての数字の組を見つける

投稿日: 2019-10-18 2019-11-05
タグ: Algorithms, Java

1概要

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

最初のアプローチでは、一意性に関係なく、このようなペアをすべて見つけます。 2つ目は、重複したペアを削除して、一意の番号の組み合わせのみを見つけることです。

それぞれのアプローチについて、

__for

__loopsを使用する従来の実装と、Java 8 Stream APIを使用する2つの実装の2つを紹介します。

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

整数の配列を繰り返し処理し、ブルートフォースのネストループアプローチを使用して、指定された数（

sum

）になるすべてのペア（

i

と

j

）を見つけます。 ** このアルゴリズムは

O（n ^ 2 ^）

の実行時複雑度を持ちます。

デモでは、次の

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 Stream API

を使った実装も書きましょう** 。

ここでは、メソッドの

_IntStream.range

を使用して、数字の連続ストリームを生成します。それから、私達は私達の条件のためにそれらをフィルタリングします:

number 1 + number 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}

従来のループを使用する場合は、次のようになります。**

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）

を使用することになります。

それでは、Java 8とStream APIを使用して問題を解決しましょう。

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つの異なるソリューションを見ました。

いつものように、この記事に示されているすべてのコードサンプルはhttps://github.com/eugenp/tutorials/tree/master/java-numbers[GitHubで見つけることができます] – これはMavenプロジェクトです。コンパイルして実行します。

getdocs

8681