Leetcode 15. 3Sum
Bizga sonlardan iborat nums array berilgan. Ularning içidan umumiy yiğindisi 0 ga teng böladigan va takrorlanmaydigan tripletlarni topib, array körinişida qaytaring.
Misol 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Tuşuntiriş: 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 içida takrorlanmaydigan tripletlar [-1,0,1] va [-1,-1,2].
Misol 2:**
Input: nums = [0,1,1] Output: [] Tuşuntiriş: Bittagina tripletning umumiy soni 0 dan katta bölib ketadi.
Misol 3:**
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: 3 ta 0 ning yiğindisi ham 0.
Işlaş tartibi
Eng oson varianti - bruteforce bölib, uçta sikl içida sonlarni bir biriga qöşib çiqiladi va yiğindisi 0 ga tengmi yöqmi tekşiriladi. Ammo bunda işlaş vaqti O(N3) ga teng bölib, yeçim samarali hisoblanmaydi.
Yana bir variant ikki pointerli (two pointer) yeçim. Bunda ikki sikl işlatiladi, ya'ni O(N2) vaqtda hisoblaşlar bajariladi. Ikki pointer usulini Leetcode 11. Container With Most Water masalasida ham körib ötgan edik.
Two pointer köp hollarda işlaş vaqtini O(Nx-1) gaça tuşirib beradi.
[-1,0,1,2,-1,-4] misolni körib ötamiz.
Dastlab berilgan array'ni ösiş tartibida saralaymiz. Saralaşning işlaş vaqti - O(NlogN). Dasturimizning işlaş vaqti baribir O(N2) bölgani sababli, O(NlogN) tartiblaşdan foydalaniş Big O ni oşirib yubormaydi.
Havola: O(NlogN) tartiblaş - Mergesort
Tartiblangan array - [-4, -1, -1, 0, 1, 2]. i bizda dastlabki sikl, u nums.length - 2 gaça davom etadi. j va k esa ikki pointerlar. Tuşunarliroq bölişi uçun left/right yoki start/end juftligi deb olsa ham böladi. Ular ikkinçi sikl içida, j kö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 bölolmaydi va ularning yiğindisi 0 dan kiçkina (-3). Bizga kattaroq son kerak. Şuning uçun j ni bittaga oşiramiz.
i j k
0 1 2 3 4 5
-4 -1 -1 0 1 2
-4 + -1 + 2 != 0
Bu safar ham yiğindi -3 ga teng, u 0 dan kiçkina. j ni bittaga oşiramiz.
i j k
0 1 2 3 4 5
-4 -1 -1 0 1 2
-4 + 0 + 2 != 0
Yiğindi -2 ga teng, u 0 dan kiçkina. j ni bittaga oşiramiz.
i j k
0 1 2 3 4 5
-4 -1 -1 0 1 2
-4 + 1 + 2 != 0
Yiğindi -1 ga teng, u 0 dan kiçkina. j ni bittaga oşiramiz. j = k bölib qolgani uçun kiçik sikl töxtaydi.
Katta sikl esa ikkinçi qadamga ö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
Yiğindi 0 ga teng, demak bizda birinçi triplet topildi. Triplet - [-1, -1, 2]. Uni biz funksiya yakunida qaytariladigan arrayga qöşib qöyamiz. Agar nums[j] == nums[j + 1] yoki nums[k] == nums[k - 1] bölsa, ularni taşlab ketamiz, çunki bizga duplikat tripletlar kerak emas. Söngra j ni bittaga oşiramiz, k ni bittaga kamaytiramiz.
i j k
0 1 2 3 4 5
-4 -1 -1 0 1 2
-1 + 0 + 1 == 0
Yiğindi 0 ga teng, bizda ikkinçi triplet topildi. Triplet - [-1, 0, 1]. Uni biz funksiya yakunida qaytariladigan arrayga qöşib qöyamiz. Agar nums[j] == nums[j + 1] yoki nums[k] == nums[k - 1] bölsa, ularni taşlab ketamiz, çunki bizga duplikat tripletlar kerak emas. Söngra j ni bittaga oşiramiz, k ni bittaga kamaytiramiz. j >= k bölib qolgani uçun kiçik sikl yakunlanadi. Katta sikl esa keyingi qadamga ötadi.
nums[i] == nums[i - 1], bunday holatda yana bir [-1, 0, 1] paydo böladi. Bizga dublikatlar kerak emas. Şuning uçun katta siklning bu qadamini ötkazib yuboramiz.
i j k
0 1 2 3 4 5
-4 -1 -1 0 1 2
0 + 1 + 2 != 0
Yiğindi 3 ga teng, u 0 dan katta. k ni bittaga kamaytiramiz. j == k bölib qolgani uçun kiçik sikl töxtaydi. Katta sikl ham ohirgi qadamdaligi bois (nums.length - 2) u ham yakuniga yetadi.
Dastur işini yakunlagaç, bizda [[-1, -1, 2]``, [-1, 0, 1]] javob hosil böldi.
Kod
Kommentlardan holi kod: