WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Leetcode 1. Two Sum

Algoritmlar va ma'lumot tuzilmalari nazariyasini tugatdik. Ötilmay qolib ketgan mavzularni esa masalalar yeçiş davomida örganib boramiz. Masalalarni Leetcode saytidan olamiz.

Leetcode 1. Sonlardan iborat nums array va yiğindisi target berilgan. target'ni nums array'dagi qaysi sonlarning yiğindisidan iborat ekanligini topib, ularning indeksini array körinişida qaytarişimiz kerak. Masalada javob aniq bor deb olamiz, array'dagi sonlarni qayta işlatmaymiz.

Misol:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Tuşuntiriş: nums[0] + nums[1] == 9, şuning uçun [0, 1] qaytaramiz.

Işlaş tartibi

Sodda usul bu albatta bruteforce usuli. Bunda ikki sikl içida array sonlarini qöşib çiqib, javobini target bilan soliştiramiz. Javob topilganda, ikki sikldagi iteratorlarni array körinişida qaytaramiz.

Sodda va oson! Ammo algoritmning işlaş vaqti tez emas ~ O(N2). Katta array'larda hisoblaş vaqti köpayib ketadi. Qanday qilib optimizatsiya qiliş mumkin?

Işlaşning yana bir usuli bor. Agar array'da biz körib çiqadigan har bir sonni yiğindini taşkil etadigan son deb oladigan bölsak, u holda yiğindidan sonni ayirib ikkinçi sonni topişimiz mumkin. Masalan, target = 9 holatida 9 - nums[0] = 7 böladi. 7 sonini biz qayerdadir saqlab, kerak holatda öşa yerdan öqib, tekşirib olişimiz mumkin bölsin. Tezkor öqib oliş uçun sonlarni dictionary'ga yiğamiz.

Misol yordamida tuşuntirişga harakat qilaman:

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

i = 0:
  13 - 2 = 11
  // 11 ni va i ni  keyinçalik tekşiriş uçun saqlab qöyamiz.
  comp[11] = i
  
i = 1:
  // nums[i] (7) ni dictionary'da bor-yöqligini tekşiramiz.
  comp[nums[i]] > 0
    // nums[i] agar dictionary'da topilsa,
    // demak hozirgi son va comp'da topilgan sonning yiğindisi target'ga teng böladi.
    return [comp[nums[i]], i]
  // Son topilmasa, hisoblaşlarni davom ettirib, comp'ga yiğ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] yiğindisi target'ga teng: 2 + 11 = 13
    // Javobni qaytaramiz va funksiya işini 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

Kod