streamalism.org

1. Oversikt

I denne raske opplæringen viser vi hvordan du implementerer en algoritme for å finne alle tallpar i en matrise hvis sum tilsvarer et gitt tall. Vi vil fokusere på to tilnærminger til problemet.

I den første tilnærmingen finner vi alle slike par uavhengig av unikhet. I det andre finner vi bare de unike tallkombinasjonene, og fjerner overflødige par.

For hver tilnærming presenterer vi to implementeringer - en tradisjonell implementering ved hjelp av til sløyfer, og et sekund ved hjelp av Java 8 Stream API.

2. Returner alle matchende par

Vi vil gjenta gjennom en rekke heltall, og finne alle parene (Jeg og j) som oppsummerer til gitt nummer (sum) ved hjelp av en brute-force, nestet loop-tilnærming. Denne algoritmen vil ha en kjøretidskompleksitet på O (n2).

For demonstrasjonene våre ser vi etter alle tallparene som summen er lik 6, ved hjelp av følgende inngang matrise:

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

I denne tilnærmingen bør algoritmen vår returnere:

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

I hver av algoritmene, når vi finner et målpar med tall som summerer seg til målnummeret, samler vi paret ved hjelp av en verktøymetode, addPairs (i, j).

Den første måten vi kan tenke oss å implementere løsningen på er å bruke den tradisjonelle til Løkke:

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

Dette kan være litt rudimentært, så la oss også skrive en implementering ved hjelp av Java 8 Stream API.

Her bruker vi metoden IntStream.range for å generere en sekvensiell strøm av tall. Deretter filtrerer vi dem for vår tilstand: nummer 1 + nummer 2 = sum:

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. Returner alle unike matchende par

For dette eksemplet må vi utvikle en smartere algoritme som bare returnerer de unike tallkombinasjonene, og utelater overflødige par.

For å oppnå dette legger vi til hvert element i et hash-kart (uten sortering), og sjekker først om paret allerede er vist. Hvis ikke, henter vi ut og merker det som vist (sett verdi felt som null).

Følgelig bruker det samme inngang array som før, og en målt sum av 6, skal algoritmen vår bare returnere de forskjellige tallkombinasjonene:

{2,4}, {3,3}

Hvis vi bruker en tradisjonell til loop, vi får:

Kartpar = nytt HashMap (); for (int i: input) {if (pairs.containsKey (i)) {if (pairs.get (i)! = null) {addPairs (i, sum-i); } pair.put (sum - i, null); } annet hvis (! pairs.containsValue (i)) {pair.put (sum-i, i); }}

Merk at denne implementeringen forbedrer den forrige kompleksiteten, som vi bruker bare en til løkke, så får vi På).

La oss nå løse problemet ved hjelp av Java 8 og Stream API:

Kartpar = nytt HashMap (); IntStream.range (0, input.length) .forEach (i -> {if (pair.containsKey (input [i]))) {if (pair.get (input [i])! = Null) {addPairs (input [ i], sum - inngang [i]);} pair.put (sum - input [i], null);} annet hvis (! pair.containsValue (input [i])) {pair.put (sum - input [ i], input [i]);}});

4. Konklusjon

I denne artikkelen forklarte vi flere forskjellige måter å finne alle parene som oppsummerer et gitt nummer i Java. Vi så to forskjellige løsninger, hver med to Java-kjernemetoder.

Som vanlig kan alle kodeeksemplene som vises i denne artikkelen bli funnet på GitHub - dette er et Maven-prosjekt, så det skal være enkelt å kompilere og kjøre det.