Leetcode 16. 3Sum Closest

Bizga sonlardan iborat nums array va target integer berilgan. Array ichidan yig’indisi targetga eng yaqin bo’lgan uchta integer’ni toping va javob sifatida ularning yig’indisini qaytaring.

Misol 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Tushuntirish: Target soniga yaqin son 2. (-1 + 2 + 1 = 2).

Misol 2:

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

Ishlash tartibi

Bu masalani ishlash algoritmi ham Leetcode 15. 3Sum kabi bo’ladi, ya’ni two pointer usulidan foydalanamiz. Uning qanday ishlashini oldingi masalada ko’rib o’tishingiz mumkin. Faqat 3Sum masalasidan farqli ravishda, bu yerda tripletlarni yig’maganimiz uchun, kod osonroq bo’ladi.

Kod

Optimizatsiya uchun, masalan, targetdan katta nums[i] chiqadigan bo’lsa, katta siklni yakunlash mumkin:

if (nums[i] > target) {
  break;
}

Ishlash vaqti – O(N2)