Two Sum - Leetcode (Easy)

#

Soal Two Sum di Leetcode adalah tantangan algoritmik klasik yang sering ditemukan di LeetCode. Masalah ini dapat dinyatakan sebagai berikut:

Pernyataan Masalah

#

Diberikan sebuah array bilangan bulat nums dan sebuah bilangan bulat target, kembalikan indeks dari dua angka sehingga jumlahnya sama dengan target.

kamu dapat mengasumsikan bahwa setiap input akan memiliki tepat satu solusi, dan kamu tidak boleh menggunakan elemen yang sama dua kali.

kamu dapat mengembalikan jawaban dalam urutan apa pun.

Contoh 1:

#

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Penjelasan: Karena nums[0] + nums[1] == 9, kita mengembalikan [0, 1].

Contoh 2:

#

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]

Contoh 3:

#

Input: nums = [3, 3], target = 6
Output: [0, 1]

Solusi

#

Sebelum memulai pengkodean, pastikan kamu benar-benar memahami persyaratan. kamu perlu menemukan dua indeks yang berbeda dalam array sehingga nilai-nilai yang sesuai jumlahnya sama dengan target.

Pertimbangkan Kasus

#

Pikirkan tentang kasus tepi seperti:

• Array mengandung angka negatif.
• Array memiliki kurang dari dua elemen.
• Target adalah positif atau negatif.

Ada beberapa pendekatan untuk menyelesaikan masalah ini, tetapi kita akan fokus pada dua metode yang efisien: pendekatan brute force dan pendekatan hash map.

Metode 1: Pendekatan Brute Force

#

Pendekatan brute force melibatkan pemeriksaan setiap pasangan angka yang mungkin dalam daftar untuk menentukan apakah mereka jumlahnya sama dengan target. Metode ini sederhana tetapi tidak efisien, terutama untuk array besar.

Langkah Algoritma

#

1. Iterasi melalui setiap elemen dalam array menggunakan loop.
2. Untuk setiap elemen, iterasi melalui elemen berikutnya untuk menemukan pasangan.
3. Untuk setiap pasangan, periksa apakah jumlahnya sama dengan target.
4. Jika pasangan ditemukan, kembalikan indeks mereka.

Kompleksitas Waktu dan Ruang

#

• Kompleksitas Waktu: O(n²) karena untuk setiap elemen, kamu mungkin perlu memeriksa semua elemen lainnya.
• Kompleksitas Ruang: O(1) karena tidak ada struktur data tambahan yang digunakan.

Contoh

#

Untuk nums = [2, 7, 11, 15] dan target = 9:

• Bandingkan 2 (indeks 0) dengan 7 (indeks 1): 2 + 7 = 9 (pasangan ditemukan).

Implementasi

#

def two_sum_brute_force(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

• Kompleksitas Waktu: O(n²)
• Kompleksitas Ruang: O(1)

Metode 2: Pendekatan Hash Map

#

Pendekatan hash map memanfaatkan hash map (atau kamus) untuk menyimpan indeks elemen saat kita iterasi melalui daftar. Ini memungkinkan kita untuk memeriksa apakah komplement dari angka saat ini (yaitu, target - nums[i]) ada dalam waktu konstan.

Cara Kerja Hash Map

#

Hash map adalah struktur data yang menyimpan pasangan kunci-nilai. Ini memungkinkan:

• Pencarian cepat: Kompleksitas waktu rata-rata O(1) untuk mengambil nilai berdasarkan kunci.
• Ukuran dinamis: Secara otomatis mengubah ukuran saat lebih banyak item ditambahkan.

Dalam pendekatan kita, kunci adalah angka dalam array, dan nilai adalah indeks yang sesuai.

Langkah Algoritma

#

1. Inisialisasi hash map kosong untuk menyimpan angka dan indeksnya.
2. Iterasi melalui array menggunakan loop:
   • Untuk setiap angka num pada indeks i, hitung komplementnya: complement = target - num.
   • Periksa apakah komplement ada dalam hash map:
     • Jika ada, kembalikan indeks dari komplement dan angka saat ini.
   • Jika tidak, simpan angka saat ini dan indeksnya dalam hash map.
3. Teruskan hingga pasangan ditemukan.

Kompleksitas Waktu dan Ruang

#

• Kompleksitas Waktu: O(n) karena setiap angka diproses sekali, dan pencarian di hash map adalah O(1) rata-rata.
• Kompleksitas Ruang: O(n) untuk menyimpan angka dalam hash map.

Contoh

#

Untuk nums = [2, 7, 11, 15] dan target = 9:

1. Inisialisasi num_to_index = {}.
2. Iterasi di atas nums:
   • Untuk indeks 0 (nilai 2):
     • Hitung komplement: 9 - 2 = 7. Tidak ada dalam peta.
     • Tambahkan 2 ke peta: num_to_index = {2: 0}.
   • Untuk indeks 1 (nilai 7):
     • Hitung komplement: 9 - 7 = 2. Ada dalam peta (indeks 0).
     • Kembalikan [0, 1].

Visualisasi Hash Map

#

1. Keadaan Awal:

   • num_to_index = {}

2. Setelah Memproses 2:

   • num_to_index = {2: 0}

3. Setelah Memproses 7:

   • Periksa 9 - 7 = 2 → Ditemukan dalam peta.
   • Kembalikan indeks [0, 1].

Implementasi

#

def two_sum_hash_map(nums, target):
    num_to_index = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i

• Kompleksitas Waktu: O(n)
• Kompleksitas Ruang: O(n)

Kesimpulan

#

Pendekatan hash map jauh lebih efisien dibandingkan metode brute force, terutama untuk dataset yang lebih besar. Dengan memanfaatkan pencarian waktu konstan, kita dapat menemukan dua indeks yang menjumlahkan ke target secara efektif. Memahami cara kerja hash map sangat penting, karena ini adalah alat yang kuat dalam menyelesaikan banyak masalah algoritmik.