Temukan Semua Pasangan Angka dalam Array yang Menjumlahkan Jumlah yang Diberikan di Jawa

1. Ikhtisar

Dalam tutorial singkat ini, kami akan menunjukkan cara menerapkan algoritme untuk menemukan semua pasangan angka dalam larik yang jumlahnya sama dengan angka tertentu. Kami akan fokus pada dua pendekatan untuk masalah tersebut .

Dalam pendekatan pertama, kita akan menemukan semua pasangan seperti itu terlepas dari keunikannya. Yang kedua, kita hanya akan menemukan kombinasi angka unik, menghapus pasangan yang berlebihan.

Untuk setiap pendekatan, kami akan menyajikan dua implementasi - implementasi tradisional yang menggunakan for loop, dan yang kedua menggunakan Java 8 Stream API.

2. Kembalikan Semua Pasangan yang Cocok

Kami akan mengulang melalui array bilangan bulat, menemukan semua pasangan ( i dan j ) yang menjumlahkan jumlah yang diberikan ( jumlah ) menggunakan pendekatan brute-force, nested-loop. Algoritma ini akan memiliki kompleksitas runtime O (n2) .

Untuk demonstrasi kami, kami akan mencari semua pasangan angka yang jumlahnya sama dengan 6 , menggunakan larik input berikut :

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

Dalam pendekatan ini, algoritme kami harus mengembalikan:

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

Di setiap algoritme, saat kami menemukan pasangan angka target yang jumlahnya sama dengan angka target, kami akan mengumpulkan pasangan menggunakan metode utilitas, addPairs (i, j) .

Cara pertama yang mungkin kita pikirkan untuk mengimplementasikan solusi adalah dengan menggunakan perulangan for tradisional :

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

Ini bisa jadi sedikit tidak sempurna, jadi mari kita juga menulis implementasi menggunakan Java 8 Stream API .

Di sini, kami menggunakan metode IntStream.range untuk menghasilkan aliran angka berurutan. Kemudian, kami memfilternya untuk kondisi kami: angka 1 + angka 2 = jumlah :

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. Kembalikan Semua Pasangan Pencocokan Unik

Untuk contoh ini, kita harus mengembangkan algoritme yang lebih cerdas yang hanya mengembalikan kombinasi angka unik, menghilangkan pasangan yang berlebihan .

Untuk mencapai ini, kami akan menambahkan setiap elemen ke peta hash (tanpa penyortiran), memeriksa terlebih dahulu apakah pasangan telah ditampilkan. Jika tidak, kami akan mengambil dan menandainya seperti yang ditunjukkan (setel bidang nilai sebagai null ).

Oleh karena itu, menggunakan larik masukan yang sama seperti sebelumnya, dan jumlah target 6 , algoritme kami seharusnya hanya mengembalikan kombinasi angka yang berbeda:

{2,4}, {3,3}

Jika kita menggunakan for loop tradisional , kita akan memiliki:

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

Perhatikan bahwa implementasi ini meningkatkan kompleksitas sebelumnya, karena kita hanya menggunakan satu for loop, jadi kita akan memiliki O (n) .

Sekarang mari kita selesaikan masalah menggunakan Java 8 dan Stream API:

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. Kesimpulan

Pada artikel ini, kami menjelaskan beberapa cara berbeda untuk mencari semua pasangan yang menjumlahkan bilangan tertentu di Jawa. Kami melihat dua solusi berbeda, masing-masing menggunakan dua metode inti Java.

Seperti biasa, semua contoh kode yang ditampilkan di artikel ini dapat ditemukan di GitHub - ini adalah proyek Maven, jadi seharusnya mudah untuk menyusun dan menjalankannya.