Bizga sonlardan iborat nums array berilgan. Ularning ichidan umumiy yig’indisi target ga teng bo’ladigan va takrorlanmaydigan kvadripletlarni topib, array ko’rinishida qaytaring.
Misol 1:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Misol 2:
Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]
Ishlash tartibi
Eng oson varianti – bruteforce bo’lib, to’rtta sikl ichida sonlarni bir biriga qo’shib chiqiladi va yig’indisi target ga tengmi yo’qmi tekshiriladi. Ammo bunda ishlash vaqti O(N4) ga teng bo’ladi.
Yana bir variant ikki pointerli (two pointer). Bunda uch sikl ishlatiladi, ya’ni O(N3) vaqtda hisoblashlar bajariladi. Biz bu usul haqida Leetcode 15. 3Sum masalasida tanishganimiz uchun ko’p to’xtalib o’tirmayman. 4Sum’ning 3Sum‘dan farqi – qo’shimcha bir siklning qo’shilishida xolos.
i j l r ------------- 0 1 2 3 4 5 ------------- -2 -1 0 0 1 2 -------------