Pronađi sve parove brojeva u nizu koji se zbrajaju s danim zbrojem u Javi

1. Pregled

U ovom brzom vodiču pokazat ćemo kako implementirati algoritam za pronalaženje svih parova brojeva u nizu čiji zbroj odgovara zadanom broju. Usredotočit ćemo se na dva pristupa problemu.

U prvom pristupu pronaći ćemo sve takve parove bez obzira na jedinstvenost. U drugom ćemo pronaći samo jedinstvene kombinacije brojeva, uklanjajući suvišne parove.

Za svaki pristup predstavit ćemo dvije implementacije - tradicionalnu primjenu za petlje, a drugi pomoću API-ja Java 8 Stream.

2. Vrati sve odgovarajuće parove

Ponovit ćemo niz čitavih brojeva, pronalazeći sve parove (ja i j) koji zbroje do zadanog broja (iznos) koristeći grubu silu, ugniježđenu petlju. Ovaj algoritam imat će složenost vremena izvođenja O (n2).

Za naše demonstracije tražit ćemo sve parove brojeva čiji je zbroj jednak 6, koristeći sljedeće ulazni niz:

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

U ovom bi pristupu naš algoritam trebao vratiti:

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

U svakom od algoritama, kada pronađemo ciljani par brojeva koji se zbrajaju do ciljanog broja, prikupit ćemo par uporabom korisne metode, addPairs (i, j).

Prvi način na koji bismo mogli pomisliti da implementiramo rješenje jest korištenje tradicionalnog za petlja:

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

Ovo može biti pomalo osnovno, pa napišimo i implementaciju pomoću API-ja Java 8 Stream.

Ovdje koristimo metodu IntStream.range za generiranje sekvencijalnog toka brojeva. Zatim ih filtriramo prema našem stanju: broj 1 + broj 2 = zbroj:

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. Vrati sve jedinstvene odgovarajuće parove

Za ovaj primjer morat ćemo razviti pametniji algoritam koji vraća samo jedinstvene kombinacije brojeva, izostavljajući suvišne parove.

Da bismo to postigli, dodat ćemo svaki element na hash kartu (bez sortiranja), prvo provjeravajući je li par već prikazan. Ako nije, dohvatit ćemo ga i označiti kao što je prikazano (postavljeno vrijednost polje kao null).

Sukladno tome, koristeći isti ulazni niz kao i prije, i ciljni zbroj 6, naš bi algoritam trebao vratiti samo različite kombinacije brojeva:

{2,4}, {3,3}

Ako se koristimo tradicionalnim za petlja, imat ćemo:

Parovi mapa = novi HashMap (); for (int i: input) {if (pair.containsKey (i)) {if (pair.get (i)! = null) {addPairs (i, sum-i); } pair.put (sum - i, null); } inače if (! parovi.sadržiVrijednost (i)) {parovi.put (zbroj-i, i); }}

Imajte na umu da se ova implementacija poboljšava u odnosu na prethodnu složenost, kao koristimo samo jedan za petlju, pa ćemo imati Na).

Sada ćemo riješiti problem pomoću Jave 8 i Stream API-ja:

Parovi mapa = novi 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);} else if (! pair.containsValue (input [i])) {pair.put (sum - input [ i], ulaz [i]);}});

4. Zaključak

U ovom smo članku objasnili nekoliko različitih načina kako pronaći sve parove koji zbrajaju zadani broj u Javi. Vidjeli smo dva različita rješenja, od kojih se svako koristilo dvije osnovne jezgrene metode.

Kao i obično, svi uzorci koda prikazani u ovom članku mogu se naći na GitHubu - ovo je Maven projekt, pa bi ga trebalo lako kompilirati i pokrenuti.


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