Menemukan Pasangan dengan Jumlah Tertentu
Mengungguli brute force O(n^2)
Menemukan Pasangan dengan Jumlah Tertentu adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Masalah Jumlah Pasangan
Diberikan sebuah larik dan sasaran, temukan dua nilai yang dapat melakukan add hingga hasilnya sama dengan sasaran. Ini adalah salah satu tugas pemanasan yang paling umum dalam kontes. 🔍
Cara Brute Force
Solusi yang paling jelas mencoba setiap pasangan dengan dua perulangan bersarang. Cara ini berhasil, tetapi memeriksa semua pasangan memerlukan O(n^2) dan bisa terlalu lambat.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Saat Brute Force Gagal
Dengan n mendekati 100000, O(n^2) berarti sepuluh miliar pemeriksaan dan Anda akan terkena TLE. Batasan soal memberi tahu Anda untuk mencari cara yang lebih cepat.
sort, Lalu Telusuri
Jika Anda melakukan sort pada larik terlebih dahulu, dua penunjuk dari kedua ujung dapat menyelesaikan soal ini dalam satu lintasan. Pengurutan memerlukan O(n log n), kemudian penelusuran memerlukan O(n).
a.sort()
left, right = 0, len(a) - 1Bandingkan dengan Sasaran
Pada setiap langkah, baca a[left] + a[right]. Satu angka itu menentukan pergerakan Anda berikutnya tanpa perlu menebak.
total = a[left] + a[right]Cocok Tepat: Selesai
Jika jumlahnya sama dengan sasaran, Anda telah menemukan pasangannya. Segera kembalikan pasangan tersebut karena Anda hanya memerlukan satu jawaban yang valid.
if total == target:
return (left, right)Jika Tidak, Sesuaikan
Jika jumlahnya terlalu kecil, gerakkan kiri ke kanan; jika terlalu besar, gerakkan kanan ke kiri. Urutan yang terurut menjamin setiap pergerakan membantu.
elif total < target:
left += 1
else:
right -= 1Tidak Ada Pasangan
Jika kedua penunjuk saling melewati tanpa menemukan kecocokan, tidak ada pasangan yang valid. Berakhirnya perulangan itu sendiri sudah merupakan jawaban lengkap.
Alternatif Himpunan Hash
Jika Anda harus mempertahankan indeks asli, himpunan hash lebih praktis: untuk setiap nilai, periksa apakah sasaran dikurangi nilai tersebut sudah pernah ditemukan.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Memilih Metode
Gunakan dua penunjuk saat larik sudah terurut atau dapat diurutkan; gunakan himpunan hash saat Anda memerlukan O(n) yang sesungguhnya tanpa pengurutan atau harus mempertahankan indeks.
Waspadai Duplikat
Jika suatu nilai dapat berpasangan dengan dirinya sendiri, pastikan kedua indeks Anda berbeda. Pemeriksaan singkat left != right atau i != j menghindari jebakan tersebut.
Pemeriksaan Singkat
Anda ingin mengalahkan brute force O(n^2) untuk menemukan pasangan yang jumlahnya sama dengan sasaran.
Rangkuman
Lakukan sort lalu telusuri dengan dua penunjuk untuk menemukan pasangan sasaran dalam O(n log n), atau gunakan himpunan hash untuk O(n) saat indeks penting. Pilih berdasarkan batasan soal. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menemukan Pasangan dengan Jumlah Tertentu” gratis?
Ya — teks lengkap “Menemukan Pasangan dengan Jumlah Tertentu” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Menemukan Pasangan dengan Jumlah Tertentu”?
Mengungguli brute force O(n^2) Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Menemukan Pasangan dengan Jumlah Tertentu” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Two Pointer pada Array Terurut
- Menemukan Pasangan dengan Jumlah Tertentu
- Menghapus Duplikat di Tempat
- Menggabungkan Dua Urutan Terurut