Langsung ke konten
Hash map: hitung dan cari

Pelajaran 4.4

Two sum dengan map

7 menit · 8 langkah

  1. Langkah 1 dari 8 · Penjelasan

    Soal: "Return index dua angka yang jumlahnya target." Brute force mengecek semua pasangan, O(n²).

    Dengan map, balik pertanyaannya. Untuk setiap angka x, pasangannya pasti target - x. Tanya map: "sudah pernah lihat target - x?" Kalau belum, simpan x beserta index-nya, lalu lanjut. Satu kali jalan, O(n).

  2. Langkah 2 dari 8 · Tebak hasilnya

    Apa yang di-return untuk [3, 2, 4] dan target 6?

    function solution(nums, target) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i]    if (seen.has(need)) {      return [seen.get(need), i]    }    seen.set(nums[i], i)  }}
    1. [1, 2]
    2. [0, 0]
    3. [2, 1]

  3. Langkah 3 dari 8 · Tebak hasilnya

    Apa yang di-return untuk [3, 3] dan target 6?

    function solution(nums, target) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i]    if (seen.has(need)) {      return [seen.get(need), i]    }    seen.set(nums[i], i)  }}
    1. [0, 1]
    2. [1, 1]
    3. [0, 0]

  4. Langkah 4 dari 8 · Cari bug-nya

    Kode ini mencari index dua angka yang jumlahnya target. Untuk [3, 2, 4] dan target 6, ia me-return [0, 0], padahal harusnya [1, 2]. Ketuk baris yang ada di tempat yang salah.

    function solution(nums, target) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    seen.set(nums[i], i)    const need = target - nums[i]    if (seen.has(need)) return [seen.get(need), i]  }}

  5. Langkah 5 dari 8 · Telusuri kodenya

    Isi i dan need di langkah yang ditandai, untuk [1, 5, 3, 7] dan target 10.

    function solution(nums, target) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i]    if (seen.has(need)) {      return [seen.get(need), i]    }    seen.set(nums[i], i)  }}

    solution([1, 5, 3, 7], 10)

  6. Langkah 6 dari 8 · Pilih pendekatan

    "Return index dua angka di nums yang jumlahnya target." Constraint: 2 ≤ nums.length ≤ 10⁵, tepat satu jawaban, return index aslinya.
    Cara mana yang tepat?

    1. Map dari angka ke index, satu kali jalan
    2. Semua pasangan dengan dua loop
    3. Set berisi semua angka
    4. Sort, lalu cari dari kedua ujung

  7. Langkah 7 dari 8 · Susun kodenya

    Versi lebih sulit: return berapa pasangan (i, j) dengan i < j yang jumlahnya target. Map menyimpan hitungan, bukan index. Satu baris tidak termasuk.

    counts.set(x, (counts.get(x) || 0) + 1)}}return pairsfor (const x of nums) {pairs += counts.get(target - x) || 0function solution(nums, target) {let pairs = 0pairs += counts.has(target - x) ? 1 : 0const counts = new Map()

  8. Langkah 8 dari 8 · Ringkasan

    • Balik pertanyaannya: untuk setiap x, cari target - x yang sudah lewat.
    • Cek dulu, baru simpan. Itu mencegah angka berpasangan dengan dirinya sendiri.
    • Simpan apa yang dibutuhkan jawaban. Index untuk "di mana", hitungan untuk "berapa banyak".

    Kartu pola

    Cari pasangannya di map
    Kapan dipakai: Saat soal mencari dua item yang cocok (jumlah, selisih, pasangan) dan brute force O(n²) terlalu lambat.
    const seen = new Map()for (let i = 0; i < nums.length; i++) {  const need = target - nums[i]  if (seen.has(need)) return [seen.get(need), i]  seen.set(nums[i], i)}