WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Leetcode 18. 4Sum

Bizga sonlardan iborat nums array berilgan. Ularning içidan umumiy yiğindisi target ga teng böladigan va takrorlanmaydigan kvadripletlarni topib, array körinişida 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]]

Işlaş tartibi

Eng oson varianti – bruteforce bölib, törtta sikl içida sonlarni bir biriga qöşib çiqiladi va yiğindisi target ga tengmi yöqmi tekşiriladi. Ammo bunda işlaş vaqti O(N4) ga teng böladi.

Yana bir variant ikki pointerli (two pointer). Bunda uç sikl işlatiladi, ya’ni O(N3) vaqtda hisoblaşlar bajariladi. Biz bu usul haqida Leetcode 15. 3Sum masalasida tanişganimiz uçun köp töxtalib ötirmayman. 4Sum'ning 3Sum'dan farqi - qöşimça bir siklning qöşilişida xolos.

i j l r

0 1 2 3 4 5

-2 -1 0 0 1 2

Kod