Bizga sonlardan iborat nums array berilgan. Ularning ichidan umumiy yig’indisi 0 ga teng bo’ladigan va takrorlanmaydigan tripletlarni topib, array ko’rinishida qaytaring.
Misol 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Tushuntirish: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. Ular ichida takrorlanmaydigan tripletlar [-1,0,1] va [-1,-1,2].
Misol 2:
Input: nums = [0,1,1] Output: [] Tushuntirish: Bittagina tripletning umumiy soni 0 dan katta bo'lib ketadi.
Misol 3:
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: 3 ta 0 ning yig'indisi ham 0.
Ishlash tartibi
Eng oson varianti – bruteforce bo’lib, uchta sikl ichida sonlarni bir biriga qo’shib chiqiladi va yig’indisi 0 ga tengmi yo’qmi tekshiriladi. Ammo bunda ishlash vaqti O(N3) ga teng bo’lib, yechim samarali hisoblanmaydi.
Yana bir variant ikki pointerli (two pointer) yechim. Bunda ikki sikl ishlatiladi, ya’ni O(N2) vaqtda hisoblashlar bajariladi. Ikki pointer usulini Leetcode 11. Container With Most Water masalasida ham ko’rib o’tgan edik.
Two pointer ko’p hollarda ishlash vaqtini O(Nx-1) gacha tushirib beradi.
[-1,0,1,2,-1,-4] misolni ko’rib o’tamiz.
Dastlab berilgan array’ni o’sish tartibida saralaymiz. Saralashning ishlash vaqti – O(NlogN). Dasturimizning ishlash vaqti baribir O(N2) bo’lgani sababli, O(NlogN) tartiblashdan foydalanish Big O ni oshirib yubormaydi.
Havola: O(NlogN) tartiblash – Mergesort
Tartiblangan array – [-4, -1, -1, 0, 1, 2]. i bizda dastlabki sikl, u nums.length - 2 gacha davom etadi. j va k esa ikki pointerlar. Tushunarliroq bo’lishi uchun left/right yoki start/end juftligi deb olsa ham bo’ladi. Ular ikkinchi sikl ichida, j ko’payib, k kamayib boradi.
i j k -------------- 0 1 2 3 4 5 -------------- -4 -1 -1 0 1 2 -------------- -4 + -1 + 2 != 0
-4 + -1 + 2 != 0 , nums[i], nums[j] va nums[k] sonlari triplet bo’lolmaydi va ularning yig’indisi 0 dan kichkina (-3). Bizga kattaroq son kerak. Shuning uchun j ni bittaga oshiramiz.
i j k -------------- 0 1 2 3 4 5 -------------- -4 -1 -1 0 1 2 -------------- -4 + -1 + 2 != 0
Bu safar ham yig’indi -3 ga teng, u 0 dan kichkina. j ni bittaga oshiramiz.
i j k -------------- 0 1 2 3 4 5 -------------- -4 -1 -1 0 1 2 -------------- -4 + 0 + 2 != 0
Yig’indi -2 ga teng, u 0 dan kichkina. j ni bittaga oshiramiz.
i j k -------------- 0 1 2 3 4 5 -------------- -4 -1 -1 0 1 2 -------------- -4 + 1 + 2 != 0
Yig’indi -1 ga teng, u 0 dan kichkina. j ni bittaga oshiramiz. j = k bo’lib qolgani uchun kichik sikl to’xtaydi.
Katta sikl esa ikkinchi qadamga o’tadi: i = 1, j = i + 1, k = nums.length - 1.
i j k -------------- 0 1 2 3 4 5 -------------- -4 -1 -1 0 1 2 -------------- -1 + -1 + 2 == 0
Yig’indi 0 ga teng, demak bizda birinchi triplet topildi. Triplet – [-1, -1, 2]. Uni biz funksiya yakunida qaytariladigan arrayga qo’shib qo’yamiz. Agar nums[j] == nums[j + 1] yoki nums[k] == nums[k - 1] bo’lsa, ularni tashlab ketamiz, chunki bizga duplikat tripletlar kerak emas. So’ngra j ni bittaga oshiramiz, k ni bittaga kamaytiramiz.
i j k -------------- 0 1 2 3 4 5 -------------- -4 -1 -1 0 1 2 -------------- -1 + 0 + 1 == 0
Yig’indi 0 ga teng, bizda ikkinchi triplet topildi. Triplet – [-1, 0, 1]. Uni biz funksiya yakunida qaytariladigan arrayga qo’shib qo’yamiz. Agar nums[j] == nums[j + 1] yoki nums[k] == nums[k - 1] bo’lsa, ularni tashlab ketamiz, chunki bizga duplikat tripletlar kerak emas. So’ngra j ni bittaga oshiramiz, k ni bittaga kamaytiramiz. j >= k bo’lib qolgani uchun kichik sikl yakunlanadi. Katta sikl esa keyingi qadamga o’tadi.
nums[i] == nums[i - 1], bunday holatda yana bir [-1, 0, 1] paydo bo’ladi. Bizga dublikatlar kerak emas. Shuning uchun katta siklning bu qadamini o’tkazib yuboramiz.
i j k -------------- 0 1 2 3 4 5 -------------- -4 -1 -1 0 1 2 -------------- 0 + 1 + 2 != 0
Yig’indi 3 ga teng, u 0 dan katta. k ni bittaga kamaytiramiz. j == k bo’lib qolgani uchun kichik sikl to’xtaydi. Katta sikl ham ohirgi qadamdaligi bois (nums.length - 2) u ham yakuniga yetadi.
Dastur ishini yakunlagach, bizda [, [-1, -1, 2][-1, 0, 1]] javob hosil bo’ldi.
Kod
Kommentlardan holi kod: