Cara Menyelesaikan Problem Two Sum di JavaScript

Pendahuluan

Problem Two Sum merupakan salah satu soal yang kerap muncul dalam wawancara pemrograman. Diberikan sebuah array bilangan bulat (nums) dan sebuah nilai target, tugas kita adalah menemukan dua angka dalam array yang jika dijumlahkan menghasilkan nilai target. Fungsi ini harus mengembalikan indeks dari kedua angka tersebut. Asumsikan bahwa setiap input hanya memiliki satu solusi dan kita tidak boleh menggunakan elemen yang sama lebih dari sekali.

Contoh Kasus

Berikut ini beberapa contoh untuk memberikan gambaran tentang cara kerja solusi:

• Contoh 1:

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

• Contoh 2:

  • Input: nums = [4,1,3], target = 5
  • Output: [0,1]
  • Penjelasan: Karena nums[0] + nums[1] == 5, maka hasil yang dikembalikan adalah [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 dengan Hash Map

Untuk menyelesaikan masalah ini dengan lebih efisien, kita bisa menggunakan hash map. Dengan pendekatan ini, kita dapat menyimpan elemen-elemen yang sudah dilihat dan mencari pasangan (complement) dari setiap elemen dalam sekali iterasi. Ini akan mengoptimalkan waktu komputasi menjadi O(n), berbeda dengan O(n²) jika kita menggunakan metode dua loop bersarang.

Kode Solusi dalam JavaScript:

function twoSum(nums, target) {
    const hashMap = new Map();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (hashMap.has(complement)) {
            return [hashMap.get(complement), i];
        }
        hashMap.set(nums[i], i);
    }

    return [];
}

Penjelasan Kode:

• Hash Map: Kita menggunakan hash map untuk menyimpan elemen-elemen yang sudah diproses, dengan nilai elemen sebagai kunci dan indeksnya sebagai nilai.
• Pencarian Pasangan: Untuk setiap elemen num dalam array, kita menghitung pasangan yang melengkapi (complement) nilai target (yaitu target - num). Jika pasangan tersebut sudah ada dalam hash map, maka kita telah menemukan pasangan yang jumlahnya sama dengan target.
• Mengembalikan Indeks: Jika ditemukan pasangan yang cocok, kita mengembalikan indeks dari kedua elemen tersebut.
• Efisiensi: Algoritma ini hanya memerlukan satu kali iterasi melalui array, sehingga jauh lebih efisien dibandingkan dengan menggunakan loop bersarang.

Kompleksitas:

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

Kamu bisa mencoba implementasi di atas dan mengujinya langsung di platform seperti LeetCode. LeetCode menyediakan alat untuk menulis, menjalankan, dan menguji solusi untuk masalah Two Sum. Jangan ragu untuk mencoba berbagai solusi dan melihat bagaimana performanya di berbagai kasus uji.

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

Kesimpulan

Pendekatan hash map ini sangat efisien untuk menyelesaikan masalah Two Sum karena mengurangi waktu eksekusi menjadi O(n). Dengan hanya satu kali iterasi, kita dapat menemukan dua elemen yang jumlahnya sama dengan target, menjadikannya solusi yang tepat untuk digunakan pada dataset yang besar.

Jika kamu tertarik mempelajari lebih lanjut tentang algoritma dalam JavaScript, pastikan untuk melihat artikel lainnya di blog ini!

Artikel ini sudah diparafrase agar tidak terkena duplicate namun tetap memberikan penjelasan yang sama.