[JAVA] 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

Screen Shot 2020-01-02 at 17.09.26.png 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.

Screen Shot 2020-01-02 at 17.27.30.png Screen Shot 2020-01-02 at 17.28.07.png Screen Shot 2020-01-02 at 17.28.19.png Maintenant, la somme de 10 de Target et des deux éléments 2 et 8 dans HashSet est 10, donc la boucle se termine et retourne true.

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 Screen Shot 2020-01-02 at 17.33.37.png

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes