アルゴリズム体操10

Sum of Two Values

整数の配列とある値を指定して、配列の二つの要素の合計が指定された値に等しくなるかどうかを判別します。

説明

CASE1: Target = 10の場合は2 + 8 = 10 となるので　true を返します。
CASE2: Target = 20の場合は二つのペアが見つからないので false を返します。

Solution

Runtime Complexity O(n)

配列全体を1回スキャンして、訪問した要素をハッシュセットに保存します。
スキャン中、配列内の要素 'e'について、ハッシュセットに 'val - e'が存在するかどうか、
つまり 'val - e'が既にアクセスされているかどうかを確認します。
ハッシュセットで val - eが見つかった場合、配列内にペア（e、val-e）があり、
その合計が指定されたvalと等しいことを意味します。よって true を返します。
配列内のすべての要素を使い果たし、そのようなペアが見つからなかった場合はfalseを返します。

Memory Complexity O(n)

配列の要素分が入るHashSet を使うので、メモリはO(n)となります。

例

最初の例、つまり値= 10でこのアルゴリズムを実行してみましょう。

ここで、Targetの10とHashSetの中にある二つの要素2, 8の合計が10となるのでループは終了してtrueを返します。

実装

findSum.java

import java.util.HashSet;
import java.util.Set;

public class findSum {
    public boolean find_sum_of_two(int[] A, int val) {
        Set<Integer> found_values = new HashSet<>();
        for (int a: A) {
            if (found_values.contains(val - a)) {
                return true;
            }
            found_values.add(a);
        }
        return false;
    }
}

Main.java

public class Main {

    static findSum algo = new findSum();

    static void test(int[] v, int val) {
        boolean output = algo.find_sum_of_two(v, val);
        System.out.println("exist(A, " + val + ") = " + (output ? "true" : "false") + "\n");
    }

    public static void main(String[] args) {
        int[] v = new int[]{2, 1, 8, 4, 7, 3};
        test(v, 3);
        test(v, 20);
        test(v, 1);
        test(v, 2);
        test(v, 7);
    }
}

Output