[LeetCode Case] Two Sum Problem

Hai sobat ngodingdirumah…

Udah lama ni ga nulis di blog ini hehe. Kita akan coba aktifkan kembali blog ngoding ini ya, itung itung buat belajar lagi udah lama ga ngulang ngulang.

Kita akan coba hadirkan series baru, yaitu code code untuk belajar kasus LeetCode.

Buat kamu yang belom tau LeetCode itu apa, coba cek ke link ini

Kasus pertama yang akan kita bahas adalah Two Sum.

Deskripsi kasusnya adalah sebagai berikut :

1. Kita diberikan sebuah array yang berisikan integer dengan nama nums, dan sebuah nilai integer dengan nama variabel target.
2. Diminta untuk mencari urutan dari isi array yang menghasilkan nilai target
3. Asumsikan hanya ada satu solusi dari urutan yang diberikan
4. Tidak boleh menggunakan elemen array yang sama
5. Follow Up: Dapatkah kita menemukan algoritma dengan kompleksitas waktu yang kurang dari O(n2)?

Nah masalah ini lumayan asik untuk diselesaikan.

Kita haruslah mencari terlebih dahulu posisi dari array yang menghasilkan nilai yang sama dengan si target. Untuk mencarinya, kita haruslah menambahkan dua elemen dari array dengan melakukan looping diantara semua elemen. Semakin banyak elemen di dalam array, maka nilai looping akan semakin tinggi.

kita akan mulai code

class Solution(object):
    def twoSum(self, nums, target):
       nums_index = [(v, index) for index, v in enumerate(nums)]
       nums_index.sort()
       begin, end = 0, len(nums) - 1
       while begin < end:
           num_target = nums_index[begin][0] + nums_index[end][0]
           if num_target == target:
               return [nums_index[begin][1], nums_index[end][1]]
           elif num_target < target:
               begin += 1
           else:
               end -= 1

Awal mula, kita akan melakukan pemetaan untuk seluruh nilai di dalam list. Pemetaan ini akan kita masukan ke dalam sebuah list baru dengan nama nums_index

   nums_index = [(v, index) for index, v in enumerate(nums)]
   nums_index.sort()

Section ini adalah deklarasi untuk membuat list yang berisi nilai indeks angka di dalam list nums, dan nilai posisinya. Seluruh nilai pemetaan di dalam di list ini selanjutnya akan diurutkan terlebih dahulu, hal ini ditujukan untuk memudahkan untuk looping selanjutnya.

   begin, end = 0, len(nums) - 1

Deklarasi variabel selanjutnya adalah menentukan nilai awal dan nilai akhir untuk looping. Nilai awal kita beri 0, dan nilai akhir adalah panjang dari list nums yang diberikan dikurangi 1.

 while begin < end:
           num_target = nums_index[begin][0] + nums_index[end][0]

Kita akan mulai code dengan melakukan kondisi while dimana nilai awal masih lebih kecil daripada nilai akhir. Untuk setiap perulangan, kita akan membuat kondisi sebuah variabel baru dengan nama num_target yang merupakan nilai penjumlahan dari indeks pemetaan yang telah kita urutkan di awal dan di akhirnya.

           if num_target == target:
               return [nums_index[begin][1], nums_index[end][1]]
           elif num_target < target:
               begin += 1
           else:
               end -= 1

Kondisi inilah penentu untuk mengambil nilai dari posisi untuk setiap penjumlahan dua elemen di dalam list yang menghasilkan jumlah sesuai dengan nilai target. Jika kondisi penjumlahan nilai pemetaan sama dengan nilai target, maka kita akan mengembalikan nilai dari posisi elemen tersebut (telah kita masukan ke dalam posisi pemetaan). Jika nilai num_target lebih kecil, maka kita akan menambahkan nilai awal, jika lebih besar kita akan mengurangi nilai akhir. Hal ini kita lakukan untuk mengondisikan penjumlahan ke atas atau ke bawah dikarenakan sebelumnya kita sudah melakukan pengurutan dari elemen yang kita petakan.

Hasil yang kita dapatkan adalah hasil yang cukup baik dan diterima oleh sistem.

Oke sekian untuk LeetCode Case kali ini.

Happy coding…