Leetcode 1. Two Sum

Algoritmlar va ma’lumot tuzilmalari nazariyasini tugatdik. O’tilmay qolib ketgan mavzularni esa masalalar yechish davomida o’rganib boramiz. Masalalarni Leetcode saytidan olamiz.

Leetcode 1. Sonlardan iborat nums array va yig’indisi target berilgan. target‘ni nums array’dagi qaysi sonlarning yig’indisidan iborat ekanligini topib, ularning indeksini array ko’rinishida qaytarishimiz kerak. Masalada javob aniq bor deb olamiz, array’dagi sonlarni qayta ishlatmaymiz.

Misol:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Tushuntirish: nums[0] + nums[1] == 9, shuning uchun [0, 1] qaytaramiz.

Ishlash tartibi

Sodda usul bu albatta bruteforce usuli. Bunda ikki sikl ichida array sonlarini qo’shib chiqib, javobini target bilan solishtiramiz. Javob topilganda, ikki sikldagi iteratorlarni array ko’rinishida qaytaramiz.

Sodda va oson! Ammo algoritmning ishlash vaqti tez emas ~ O(N²). Katta array’larda hisoblash vaqti ko’payib ketadi. Qanday qilib optimizatsiya qilish mumkin?

Ishlashning yana bir usuli bor. Agar array’da biz ko’rib chiqadigan har bir sonni yig’indini tashkil etadigan son deb oladigan bo’lsak, u holda yig’indidan sonni ayirib ikkinchi sonni topishimiz mumkin. Masalan, target = 9 holatida 9 - nums[0] = 7 bo’ladi. 7 sonini biz qayerdadir saqlab, kerak holatda o’sha yerdan o’qib, tekshirib olishimiz mumkin bo’lsin. Tezkor o’qib olish uchun sonlarni dictionary’ga yig’amiz.

Misol yordamida tushuntirishga harakat qilaman:

nums = [2,7,11,15], target = 13
comp = {}

i = 0: 
  13 - 2 = 11
  // 11 ni va i ni  keyinchalik tekshirish uchun saqlab qo'yamiz.
  comp[11] = i
  
i = 1:
  // nums[i] (7) ni dictionary'da bor-yo'qligini tekshiramiz.
  comp[nums[i]] > 0
    // nums[i] agar dictionary'da topilsa, 
    // demak hozirgi son va comp'da topilgan sonning yig'indisi target'ga teng bo'ladi.
    return [comp[nums[i]], i]
  // Son topilmasa, hisoblashlarni davom ettirib, comp'ga yig'ib boramiz.
  13 - 7 = 6
  comp[6] = 1

i = 2:
  comp[nums[i]] > 0 
    // 11 dictionary'da topildi. Uning qiymati 0. 
    // Demak nums[0] va nums[2] yig'indisi target'ga teng: 2 + 11 = 13
    // Javobni qaytaramiz va funksiya ishini tugatamiz. 
    return [comp[nums[i]], i]
  comp[target - nums[i]] = i

i = 3:
  comp[nums[i]] > 0 
    return [comp[nums[i]], i]
  comp[target - nums[i]] = i

Ishlash tartibi

Kod