Trova tutte le coppie di numeri in una matrice che si sommano a una data somma in Java

1. Panoramica

In questo rapido tutorial, mostreremo come implementare un algoritmo per trovare tutte le coppie di numeri in un array la cui somma è uguale a un dato numero. Ci concentreremo su due approcci al problema .

Nel primo approccio, troveremo tutte queste coppie indipendentemente dall'unicità. Nella seconda, troveremo solo le combinazioni di numeri univoci, rimuovendo le coppie ridondanti.

Per ogni approccio, presenteremo due implementazioni: un'implementazione tradizionale che utilizza i cicli for e una seconda che utilizza l'API Java 8 Stream.

2. Restituisci tutte le coppie corrispondenti

Eseguiremo un'iterazione attraverso un array di numeri interi, trovando tutte le coppie ( i e j ) che si sommano al numero dato ( somma ) usando un approccio a ciclo nidificato a forza bruta. Questo algoritmo avrà una complessità di runtime di O (n2) .

Per le nostre dimostrazioni, cercheremo tutte le coppie di numeri la cui somma è uguale a 6 , utilizzando il seguente array di input :

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

In questo approccio, il nostro algoritmo dovrebbe restituire:

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

In ciascuno degli algoritmi, quando troviamo una coppia target di numeri che si somma al numero target, raccoglieremo la coppia utilizzando un metodo di utilità, addPairs (i, j) .

Il primo modo in cui potremmo pensare di implementare la soluzione è utilizzare il tradizionale ciclo for :

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])); } } }

Questo può essere un po 'rudimentale, quindi scriviamo anche un'implementazione utilizzando l'API Java 8 Stream .

Qui utilizziamo il metodo IntStream.range per generare un flusso sequenziale di numeri. Quindi, li filtriamo per la nostra condizione: numero 1 + numero 2 = somma :

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. Restituisci tutte le coppie corrispondenti univoche

Per questo esempio, dovremo sviluppare un algoritmo più intelligente che restituisca solo le combinazioni di numeri univoche, omettendo le coppie ridondanti .

Per ottenere ciò, aggiungeremo ogni elemento a una mappa hash (senza ordinamento), controllando prima se la coppia è già stata mostrata. In caso contrario, lo recupereremo e lo contrassegneremo come mostrato (imposta il campo valore come null ).

Di conseguenza, utilizzando lo stesso array di input di prima e una somma target di 6 , il nostro algoritmo dovrebbe restituire solo le diverse combinazioni di numeri:

{2,4}, {3,3}

Se usiamo un ciclo for tradizionale , avremo:

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); } }

Si noti che questa implementazione migliora la complessità precedente, poiché usiamo solo un ciclo for , quindi avremo O (n) .

Ora risolviamo il problema utilizzando Java 8 e 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. Conclusione

In questo articolo, abbiamo spiegato diversi modi per trovare tutte le coppie che sommano un dato numero in Java. Abbiamo visto due diverse soluzioni, ciascuna utilizzando due metodi di base Java.

Come al solito, tutti gli esempi di codice mostrati in questo articolo possono essere trovati su GitHub: questo è un progetto Maven, quindi dovrebbe essere facile compilarlo ed eseguirlo.