Lanjut55 XPUnit 7: Daftar dan Array, soal 11 dari 12
Pasangan Jumlah Target
Hitung banyaknya pasangan angka yang jumlahnya sama dengan target.
Di permainan kartu angka, dua kartu yang jumlahnya tepat sama dengan angka target boleh dibuang bersama. Ada berapa pasangan kartu yang memenuhi?
Masukan
Baris pertama berisi N (1 sampai 20000) dan bilangan bulat T, angka target. Baris kedua berisi N bilangan bulat dari -1000000 sampai 1000000.
Keluaran
Banyaknya pasangan posisi i < j dengan data[i] + data[j] = T.
Contoh masukan dan keluaran
Contoh 1
Masukan
6 7 1 6 3 4 2 5
Keluaran
3
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Memeriksa semua pasangan butuh sekitar 200 juta pemeriksaan untuk 20000 kartu, terlalu lama. Cari cara yang cukup sekali jalan.
Petunjuk 2
Saat melihat kartu x, kartu pasangannya adalah T - x. Simpan berapa kali setiap angka sudah muncul di dictionary.