Gymnastique algorithmique 10

Sum of Two Values Spécifiez un tableau d'entiers et une valeur pour déterminer si la somme des deux éléments du tableau est égale à la valeur spécifiée.

La description

CASE1: lorsque Target = 10, 2 + 8 = 10, donc true est renvoyé. CASE2: Si Target = 20, les deux paires ne sont pas trouvées et false est renvoyé.

Solution Runtime Complexity O(n) Analyse le tableau entier une fois et enregistre les éléments visités dans un hashset. Que "val --e" soit présent dans le hashset de l'élément "e" dans le tableau pendant le scan, Autrement dit, vérifiez si "val --e" est déjà accédé. Si val --e est trouvé dans le hashset, alors il y a une paire (e, val-e) dans le tableau et Cela signifie que la somme est égale à la valeur spécifiée. Donc ça retourne vrai. Renvoie false si tous les éléments du tableau sont épuisés et qu'aucune paire de ce type n'est trouvée. Memory Complexity O(n) La mémoire est O (n) car nous utilisons HashSet qui contient les éléments du tableau.

Exemple

Exécutons cet algorithme avec le premier exemple, value = 10.

la mise en oeuvre

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