Algorithmusgymnastik 10

Sum of Two Values Geben Sie ein Array aus Ganzzahlen und einen Wert an, um festzustellen, ob die Summe der beiden Elemente des Arrays dem angegebenen Wert entspricht.

Erläuterung

FALL1: Wenn Ziel = 10, 2 + 8 = 10, wird true zurückgegeben. FALL 2: Wenn Ziel = 20, werden die beiden Paare nicht gefunden und false wird zurückgegeben.

Solution Runtime Complexity O(n) Scannt das gesamte Array einmal und speichert die besuchten Elemente in einem Hashset. Gibt an, ob 'val - e' im Hashset für element'e 'im Array während des Scans vorhanden ist Überprüfen Sie also, ob auf 'val --e' bereits zugegriffen wird. Wenn val - e im Hashset gefunden wird, befindet sich ein Paar (e, val-e) im Array und Dies bedeutet, dass die Summe dem angegebenen Wert entspricht. Es gibt also true zurück. Gibt false zurück, wenn alle Elemente im Array erschöpft sind und kein solches Paar gefunden wird. Memory Complexity O(n) Der Speicher ist O (n), weil wir HashSet verwenden, das die Elemente des Arrays enthält.

Beispiel

Lassen Sie uns diesen Algorithmus mit dem ersten Beispiel ausführen, Wert = 10.

Implementierung

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