streamalism.org

1. Overzicht

In deze korte tutorial laten we zien hoe je een algoritme implementeert voor het vinden van alle paren getallen in een array waarvan de som gelijk is aan een bepaald getal. We zullen ons concentreren op twee benaderingen van het probleem.

In de eerste benadering zullen we al dergelijke paren vinden, ongeacht hun uniciteit. In de tweede vinden we alleen de unieke cijfercombinaties, waardoor overtollige paren worden verwijderd.

Voor elke benadering presenteren we twee implementaties - een traditionele implementatie met voor loops, en een seconde met behulp van de Java 8 Stream API.

2. Retourneer alle overeenkomende paren

We doorlopen een reeks gehele getallen en vinden alle paren (ik en j) die optellen tot het opgegeven aantal (som) met behulp van een brute-force, geneste-lusbenadering. Dit algoritme heeft een runtime-complexiteit van O (n2).

Voor onze demonstraties zoeken we naar alle getallenparen waarvan de som gelijk is aan 6, met behulp van het volgende invoer matrix:

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

In deze benadering zou ons algoritme moeten retourneren:

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

Wanneer we in elk van de algoritmen een doelpaar van getallen vinden die samen het doelnummer vormen, verzamelen we het paar met behulp van een hulpprogramma-methode, addPairs (i, j).

De eerste manier waarop we zouden kunnen denken om de oplossing te implementeren, is door de traditionele te gebruiken voor lus:

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

Dit kan een beetje rudimentair zijn, dus laten we ook een implementatie schrijven met behulp van de Java 8 Stream API.

Hier gebruiken we de methode IntStream.-bereik om een ​​opeenvolgende stroom getallen te genereren. Vervolgens filteren we ze op onze toestand: nummer 1 + nummer 2 = som:

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

3. Retourneer alle unieke overeenkomende paren

Voor dit voorbeeld zullen we moeten ontwikkel een slimmer algoritme dat alleen de unieke cijfercombinaties retourneert, waarbij overtollige paren worden weggelaten.

Om dit te bereiken, voegen we elk element toe aan een hash-map (zonder te sorteren), waarbij we eerst controleren of het paar al is weergegeven. Als dit niet het geval is, zullen we het ophalen en markeren zoals weergegeven (set waarde veld als nul).

Dienovereenkomstig met hetzelfde invoer array zoals eerder, en een doelsom van 6, zou ons algoritme alleen de verschillende cijfercombinaties moeten retourneren:

{2,4}, {3,3}

Als we een traditioneel gebruiken voor loop, we hebben:

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

Merk op dat deze implementatie de eerdere complexiteit verbetert, zoals we gebruiken er maar één voor loop, dus we hebben Aan).

Laten we nu het probleem oplossen met Java 8 en de Stream API:

Kaartparen = nieuwe 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);} anders if (! pairs.containsValue (input [i])) {pairs.put (sum - input [ i], voer [i]);}});

4. Conclusie

In dit artikel hebben we verschillende manieren uitgelegd om alle paren te vinden die een bepaald getal in Java samenvatten. We hebben twee verschillende oplossingen gezien, elk met twee Java-kernmethoden.

Zoals gewoonlijk zijn alle codevoorbeelden die in dit artikel worden getoond, te vinden op GitHub - dit is een Maven-project, dus het zou gemakkelijk te compileren en uit te voeren moeten zijn.