Rechercher toutes les paires de nombres dans un tableau qui s'additionnent à une somme donnée en Java

1. Vue d'ensemble

Dans ce tutoriel rapide, nous montrerons comment implémenter un algorithme pour trouver toutes les paires de nombres dans un tableau dont la somme est égale à un nombre donné. Nous allons nous concentrer sur deux approches du problème .

Dans la première approche, nous trouverons toutes ces paires indépendamment de leur caractère unique. Dans le second, nous ne trouverons que les combinaisons de nombres uniques, en supprimant les paires redondantes.

Pour chaque approche, nous présenterons deux implémentations: une implémentation traditionnelle utilisant des boucles for et une seconde utilisant l'API Java 8 Stream.

2. Renvoyer toutes les paires correspondantes

Nous allons parcourir un tableau d'entiers, trouver toutes les paires ( i et j ) qui totalisent le nombre donné ( somme ) en utilisant une approche en boucle imbriquée par force brute. Cet algorithme aura une complexité d'exécution de O (n2) .

Pour nos démonstrations, nous rechercherons toutes les paires de nombres dont la somme est égale à 6 , en utilisant le tableau d' entrée suivant :

int[] input = { 2, 4, 3, 3 }; 

Dans cette approche, notre algorithme devrait retourner:

{2,4}, {4,2}, {3,3}, {3,3}

Dans chacun des algorithmes, lorsque nous trouvons une paire cible de nombres qui totalisent le nombre cible, nous collectons la paire en utilisant une méthode utilitaire, addPairs (i, j) .

La première façon dont nous pourrions penser pour implémenter la solution est d'utiliser la boucle for traditionnelle :

for (int i = 0; i < input.length; i++) { for (int j = 0; j < input.length; j++) { if (j != i && (input[i] + input[j]) == sum) { addPairs(input[i], sum-input[i])); } } }

Cela peut être un peu rudimentaire, alors écrivons également une implémentation à l'aide de l'API Java 8 Stream .

Ici, nous utilisons la méthode IntStream.range pour générer un flux séquentiel de nombres. Ensuite, nous les filtrons pour notre condition: nombre 1 + nombre 2 = somme :

IntStream.range(0, input.length) .forEach(i -> IntStream.range(0, input.length) .filter(j -> i != j && input[i] + input[j] == sum) .forEach(j -> addPairs(input[i], input[j])) ); 

3. Renvoyer toutes les paires correspondantes uniques

Pour cet exemple, nous devrons développer un algorithme plus intelligent qui ne renvoie que les combinaisons de nombres uniques, en omettant les paires redondantes .

Pour ce faire, nous ajouterons chaque élément à une carte de hachage (sans tri), en vérifiant d'abord si la paire a déjà été affichée. Sinon, nous le récupérerons et le marquerons comme indiqué (définissez le champ de valeur comme nul ).

En conséquence, en utilisant le même tableau d' entrée que précédemment et une somme cible de 6 , notre algorithme ne devrait renvoyer que les différentes combinaisons de nombres:

{2,4}, {3,3}

Si nous utilisons une boucle for traditionnelle , nous aurons:

Map pairs = new HashMap(); for (int i : input) { if (pairs.containsKey(i)) { if (pairs.get(i) != null) { addPairs(i, sum-i); } pairs.put(sum - i, null); } else if (!pairs.containsValue(i)) { pairs.put(sum-i, i); } }

Notez que cette implémentation améliore la complexité précédente, car nous n'utilisons qu'une seule boucle for , nous aurons donc O (n) .

Résolvons maintenant le problème à l'aide de Java 8 et de l'API Stream:

Map pairs = new HashMap(); IntStream.range(0, input.length).forEach(i -> { if (pairs.containsKey(input[i])) { if (pairs.get(input[i]) != null) { addPairs(input[i], sum - input[i]); } pairs.put(sum - input[i], null); } else if (!pairs.containsValue(input[i])) { pairs.put(sum - input[i], input[i]); } });

4. Conclusion

Dans cet article, nous avons expliqué plusieurs façons différentes de trouver toutes les paires qui résument un nombre donné en Java. Nous avons vu deux solutions différentes, chacune utilisant deux méthodes de base Java.

Comme d'habitude, tous les exemples de code présentés dans cet article peuvent être trouvés sur GitHub - il s'agit d'un projet Maven, il devrait donc être facile de le compiler et de l'exécuter.