Find alle par numre i en matrix, der udgør en given sum i Java

1. Oversigt

I denne hurtige vejledning viser vi, hvordan man implementerer en algoritme til at finde alle par af tal i en matrix, hvis sum svarer til et givet antal. Vi fokuserer på to tilgange til problemet.

I den første tilgang finder vi alle sådanne par uanset unikhed. I det andet finder vi kun de unikke talekombinationer, der fjerner overflødige par.

For hver tilgang præsenterer vi to implementeringer - en traditionel implementering ved hjælp af til sløjfer og et sekund ved hjælp af Java 8 Stream API.

2. Returner alle matchende par

Vi gentager gennem en række heltal og finder alle par (jeg og j) at summen op til det givne nummer (sum) ved hjælp af en brute-force, nestet-loop tilgang. Denne algoritme har en runtime-kompleksitet på O (n2).

Til vores demonstrationer ser vi efter alle par med tal, hvis sum er lig med 6, ved hjælp af følgende input matrix:

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

I denne tilgang skal vores algoritme vende tilbage:

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

I hver af algoritmerne, når vi finder et målpar af tal, der summerer til målnummeret, samler vi parret ved hjælp af en hjælpemetode, addPairs (i, j).

Den første måde, vi måske tænker på at implementere løsningen, er ved at bruge den traditionelle 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 lidt rudimentært, så lad os også skrive en implementering ved hjælp af Java 8 Stream API.

Her bruger vi metoden IntStream.range at generere en sekventiel strøm af tal. Derefter filtrerer vi dem efter vores 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 unikke matchende par

For dette eksempel skal vi udvikle en smartere algoritme, der kun returnerer de unikke talekombinationer, idet overflødige par udelades.

For at opnå dette tilføjer vi hvert element til et hash-kort (uden sortering) og kontrollerer først, om parret allerede er vist. Hvis ikke, henter vi det og markerer det som vist (sæt værdi felt som nul).

Følgelig bruger det samme input array som før, og en målt sum af 6, skal vores algoritme kun returnere de forskellige talekombinationer:

{2,4}, {3,3}

Hvis vi bruger en traditionel til loop, vi får:

Kortpar = nyt HashMap (); for (int i: input) {if (pair.containsKey (i)) {if (pair.get (i)! = null) {addPairs (i, sum-i); } pair.put (sum - i, null); } ellers hvis (! pair.containsValue (i)) {pair.put (sum-i, i); }}

Bemærk, at denne implementering forbedrer den tidligere kompleksitet, som vi bruger kun en til løkke, så får vi det På).

Lad os nu løse problemet ved hjælp af Java 8 og Stream API:

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

4. Konklusion

I denne artikel forklarede vi flere forskellige måder at finde alle par, der opsummerer et givet nummer i Java. Vi så to forskellige løsninger, der hver anvendte to Java-kernemetoder.

Som normalt kan alle kodeeksempler, der vises i denne artikel, findes på GitHub - dette er et Maven-projekt, så det skal være let at kompilere og køre det.


$config[zx-auto] not found$config[zx-overlay] not found