Keluarga two-sum

Pola soal two-sum klasik sebagai pratinjau kekuatan hashing pada array.

Daftar isi

Soal two-sum adalah pintu masuk klasik ke pola array, diberikan sebuah array bilangan dan satu angka target, cari dua elemen yang penjumlahannya tepat target. Solusi pertamanya selalu brute force, lalu perbandingan dengan hash map menunjukkan biaya yang turun dari $O(n^2)$ ke $O(n)$ pada masukan yang sama. Topik ini mengukur kedua pendekatan dengan penghitung operasi, memperkenalkan varian array terurut, dan menutup modul array dengan kumpulan soal untuk dipraktikkan.

Soal dan pendekatan paksa#

Soalnya dinyatakan sederhana, diberikan array bilangan dan satu target, kembalikan indeks dua elemen yang penjumlahannya sama dengan target. Setiap elemen dipakai paling banyak satu kali, jawaban dijamin ada pada soal standar, dan indeksnya dilaporkan sesuai urutan kemunculan. Contoh klasiknya adalah array [2, 7, 11, 15] dengan target 9, yang dijawab oleh indeks 0 dan 1 karena $2 + 7 = 9$ .

Pendekatan brute force, yaitu mencoba semua kemungkinan tanpa penghematan apa pun, memasangkan setiap elemen dengan seluruh elemen yang berada sesudahnya. Dua perulangan bersarang menghasilkan hingga $n(n-1)/2$ pasangan yang diperiksa, sehingga biayanya $O(n^2)$ . Pada array 1.000 elemen itu sekitar 500 ribu perbandingan, dan angkanya tumbuh kuadrat ketika masukan membesar. Solusi ini selalu benar dan layak ditulis lebih dahulu, tetapi bentuk perulangan bersarangnya membekas sebagai tanda ada ruang perbaikan.

Hash map, mengingat yang sudah dilihat#

Hash map adalah struktur data yang memetakan kunci ke nilai dan memeriksa keberadaan sebuah kunci dalam waktu rata-rata $O(1)$ . Mekanisme dua perulangan bisa diringkas menjadi satu pertanyaan yang lebih cerdas, saat berdiri di elemen ke- $i$ , apakah pasangannya, yaitu target dikurangi nilai sekarang, sudah pernah terlihat sebelumnya. Pemeriksaan itu dilakukan pada hash map yang menyimpan nilai yang sudah dilalui beserta indeksnya, bukan pada sisa array, sehingga selesai dalam satu langkah.

Kalau pasangannya belum terlihat, elemen sekarang dicatat ke hash map bersama indeksnya, lalu lintasan berlanjut ke elemen berikutnya. Satu lintasan (single pass) menyelesaikan semuanya dalam $O(n)$ waktu, dengan $O(n)$ memori tambahan untuk tabelnya. Ini kompromi yang sangat lazim dalam optimasi algoritma, yaitu menukar sedikit memori demi potongan waktu yang jauh lebih besar.

Mengukur kedua pendekatan#

Klaim $O(n^2)$ lawan $O(n)$ tidak perlu dibiarkan sebagai teori, karena perbandingan yang benar-benar terjadi dapat dihitung pada masukan yang sama. Demo berikut menjalankan kedua pendekatan pada array dua belas elemen, lalu mencetak jawaban dan jumlah perbandingannya.

python two-sum-perbandingan.py

"""Dua pendekatan two-sum diukur pada masukan yang sama."""

angka = [2, 7, 11, 15, 3, 6, 8, 1, 9, 4, 13, 5]
target = 14

# pendekatan 1: brute force dengan dua perulangan bersarang
langkah_brute = 0
jawaban_brute = None
for i in range(len(angka)):
    for j in range(i + 1, len(angka)):
        langkah_brute += 1
        if angka[i] + angka[j] == target:
            jawaban_brute = (i, j)
            break
    if jawaban_brute is not None:
        break

# pendekatan 2: hash map satu lintasan
langkah_hash = 0
terlihat = {}                    # nilai -> indeks kemunculannya
jawaban_hash = None
for i, nilai in enumerate(angka):
    langkah_hash += 1
    pasangan = target - nilai
    if pasangan in terlihat:
        jawaban_hash = (terlihat[pasangan], i)
        break
    terlihat[nilai] = i

print("brute force :", jawaban_brute, "dengan", langkah_brute, "perbandingan")
print("hash map    :", jawaban_hash, "dengan", langkah_hash, "perbandingan")

text Keluaran

brute force : (2, 4) dengan 23 perbandingan
hash map    : (2, 4) dengan 5 perbandingan

Jawaban kedua pendekatan identik, indeks 2 dan 4, tetapi biayanya 23 lawan 5 perbandingan. Selisih ini membengkak cepat karena brute force tumbuh kuadrat sedangkan hash map tumbuh linear, dan pada array 100 ribu elemen dengan jawaban di ujungnya, selisihnya mencapai ribuan kali lipat. Angka pada demo kecil memang terlihat kecil, pola pertumbuhannya itulah yang menentukan pada masukan nyata.

Varian array terurut dan two pointer#

Keluarga two-sum punya varian yang menyebut arraynya sudah terurut menaik, dikenal sebagai Two Sum II. Sifat terurut membuka pendekatan two pointer yang diperkenalkan pada topik operasi in-place, kali ini tanpa hash map sama sekali. Dua penunjuk berdiri di kedua ujung array, lalu jumlah keduanya menentukan arah, kekecilan berarti ujung kiri maju, kebesaran berarti ujung kanan mundur. Setiap langkah membuang satu elemen dari pertimbangan, sehingga lintasannya hanya $O(n)$ tanpa memori tambahan.

python Contoh: two pointer pada array terurut

# Two Sum II: array sudah terurut, dua penunjuk bergerak dari kedua ujung
angka = [2, 7, 11, 15, 19, 24]   # sudah terurut menaik
target = 34
kiri, kanan = 0, len(angka) - 1
langkah = 0
jawaban = None

while kiri < kanan:
    langkah += 1
    jumlah = angka[kiri] + angka[kanan]
    if jumlah == target:
        jawaban = (kiri + 1, kanan + 1)   # soal Two Sum II memakai indeks mulai 1
        break
    if jumlah < target:
        kiri += 1     # jumlah kekecilan, geser ujung kiri ke kanan
    else:
        kanan -= 1    # jumlah kebesaran, geser ujung kanan ke kiri

print("jawaban :", jawaban)
print("langkah :", langkah)

text Keluaran

jawaban : (4, 5)
langkah : 5

Kombinasi kiri += 1 dan kanan -= 1 tidak pernah melewatkan pasangan yang sah, karena setiap keputusan memakai sifat terurut untuk menyingkirkan elemen yang mustahil menjadi jawaban. Bedakan dengan two-sum biasa yang arraynya tidak terurut, karena menyortir dahulu menghabiskan $O(n \log n)$ sekaligus mengacaukan indeks asli yang diminta soalnya. Varian ini sekaligus pratinjau pola two pointer yang dibedah lebih dalam pada modul pola array.

Pola yang dibawa ke depan#

Satu kalimat merangkum trik hash map pada topik ini, simpan yang sudah dilihat, lalu tanyakan apakah pelengkapnya pernah muncul. Pola yang sama menyelesaikan deteksi duplikat, penghitungan frekuensi, dan banyak soal subarray pada modul hashing, sehingga keluarga two-sum menjadi benihnya. Keluarga ini juga melatih kebiasaan yang lebih penting daripada jawabannya, yaitu mengukur dua solusi pada masukan yang sama sebelum memutuskan. Dengan penghitung operasi sesederhana pada demo di atas, perbedaan $O(n^2)$ dan $O(n)$ berhenti menjadi teori dan menjadi angka.

Soal untuk dipraktikkan#

Enam soal berikut menguji pola-pola yang dipakai sepanjang modul array, dari mekanisme memori sampai hash map.

Two Sum : soal dasar yang persis dikerjakan di topik ini, cocok untuk penulisan pertama pola hash map dari nol.
Two Sum II - Input Array Is Sorted : varian terurut yang menguji two pointer tanpa hash map sama sekali.
Contains Duplicate : menerapkan pola simpan-yang-sudah-dilihat dalam bentuk paling murni, cukup satu lintasan dengan hash map.
Move Zeroes : memindahkan elemen dalam array dengan operasi in-place dan dua penunjuk yang bergerak searah.
Rotate Array : rotasi tiga kali pembalikan dari topik operasi in-place dalam wujud soal aslinya.
Product of Array Except Self : pra-penghitungan dari kiri dan kanan, saudara jauh dari pola prefix sum pada topik jumlah prefiks.

Ringkasan#

Brute force two-sum memeriksa hingga $n(n-1)/2$ pasangan, sedangkan hash map satu lintasan selesai dalam $O(n)$ waktu dengan $O(n)$ memori.
Urutan periksa-pasangan-terlebih-dahulu menjaga kebenaran ketika target tepat dua kali satu nilai.
Array terurut dibuka dengan two pointer berbiaya $O(n)$ tanpa memori tambahan, seperti pada Two Sum II.
Pola simpan-yang-sudah-dilihat menjadi benih modul hashing, dan penghitung operasi menjadikan perbandingan biaya bukan teori.

Referensi#

Data Structures — Python Software Foundation — dokumentasi dict yang dipakai sebagai hash map pada demo topik ini.
VisuAlgo — visualisasi interaktif tabel hash untuk melihat mekanisme pencarian kuncinya.