Sum of Two Values

정수의 배열과 어느 값을 지정해, 배열의 2 개의 요소의 합계가 지정된 값과 동일해질지 어떨지를 판별합니다.

설명

CASE1: Target = 10이면 2 + 8 = 10이므로 true를 반환합니다.
CASE2: Target = 20이면 두 쌍을 찾을 수 없으므로 false를 반환합니다.

Solution

Runtime Complexity O(n)

전체 배열을 한 번 스캔하여 방문한 요소를 해시 세트에 저장합니다.
스캔하는 동안 배열의 요소 '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개의 요소 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