Menyelesaikan Problem Two Sum di Golang

Pendahuluan

Masalah Two Sum adalah salah satu masalah yang sering muncul dalam wawancara coding. Diberikan sebuah array bilangan bulat (nums) dan sebuah nilai target (target), tugas kita adalah mencari dua elemen dalam array yang jika dijumlahkan sama dengan target. Fungsi harus mengembalikan indeks dari dua angka tersebut, dan kita bisa mengasumsikan bahwa setiap input hanya memiliki satu solusi. Selain itu, kita tidak boleh menggunakan elemen yang sama dua kali.

Contoh Kasus

Berikut adalah beberapa contoh input dan output untuk memberikan gambaran lebih jelas:

• Contoh 1:

  • Input: nums = [9,8,2,11], target = 10
  • Output: [1,2]
  • Penjelasan: Karena nums[1] + nums[2] == 10, kita mengembalikan [1, 2].

• Contoh 2:

  • Input: nums = [4,1,3], target = 5
  • Output: [0,1]
  • Penjelasan: Karena nums[0] + nums[1] == 5, kita mengembalikan [0, 1].

• Contoh 3:

  • Input: nums = [4,4], target = 8
  • Output: [0,1]
  • Penjelasan: Karena nums[0] + nums[1] == 8, kita mengembalikan [0, 1].

Solusi Menggunakan Hash Map

Untuk menyelesaikan masalah ini secara efisien, kita bisa menggunakan hash map. Dengan hash map, kita bisa menyimpan elemen yang sudah dilihat dan mencari pasangannya (complement) dalam satu kali iterasi. Pendekatan ini mengoptimalkan waktu menjadi O(n), dibandingkan dengan O(n²) jika kita menggunakan dua loop bersarang.

Kode Solusi:

func twoSum(nums []int, target int) []int {
    hashMap := make(map[int]int)

    for i, num := range nums {
        complement := target - num
        if j, found := hashMap[complement]; found {
            return []int{j, i}
        }
        hashMap[num] = i
    }

    return []int{}
}

Penjelasan Kode:

• Hash Map: Kita membuat hash map untuk menyimpan elemen yang sudah kita lihat, di mana nilai elemen dijadikan sebagai kunci dan indeksnya sebagai nilai.
• Cari Pasangan: Untuk setiap elemen num di array, kita menghitung nilai complement (yaitu target - num). Jika complement ditemukan dalam hash map, itu berarti kita telah menemukan pasangan yang jika dijumlahkan sama dengan target.
• Return Indeks: Jika pasangan ditemukan, kita mengembalikan indeks dari kedua elemen tersebut.
• Efisiensi: Pendekatan ini memastikan bahwa kita hanya perlu melakukan satu kali iterasi melalui array.

Kompleksitas:

• Waktu: O(n), karena kita hanya mengiterasi array sekali.
• Memori: O(n), karena kita menggunakan hash map untuk menyimpan elemen yang sudah dilihat.

Kalian bisa mencoba solusi di atas dan mengujinya langsung di LeetCode. LeetCode menyediakan platform di mana Anda bisa menulis, menguji, dan submit solusi Anda untuk masalah Two Sum. Jangan ragu untuk bereksperimen dengan solusi ini dan lihat bagaimana performanya di berbagai kasus uji di LeetCode.

Berikut adalah tautan ke problem Two Sum di LeetCode: LeetCode Two Sum Problem

Kesimpulan

Kesimpulan

Pendekatan menggunakan hash map sangat efisien dalam menyelesaikan masalah Two Sum karena mengurangi waktu eksekusi menjadi O(n). Dengan algoritma ini, kita bisa menemukan pasangan elemen yang jumlahnya sesuai dengan target hanya dengan satu kali iterasi melalui array. Ini menjadikannya solusi yang ideal untuk masalah ini, terutama saat kita bekerja dengan dataset yang besar.

Jika Anda tertarik untuk mempelajari lebih lanjut tentang algoritma dalam Golang, pastikan untuk menjelajahi artikel lainnya di blog ini!