18. 4Sum

Prbolem

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

리스트 내에 4개의 원소의 합이 특정값이 되게 하는 문제
이전에 풀었떤 15. 3sum 문제의 확장판이다.
이걸 응용하면 크게 어렵지는 않았다.

Codes

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:


        N = len(nums)
        nums.sort()
        solutions = []
        
        for i in range(N-3):
            if i>0 and nums[i] == nums[i-1]:
                continue
            
            for j in range(i+1, N-2):
                if j>i+1 and nums[j] == nums[j-1]:
                    continue
            
                l = j+1
                r = N-1
                while l<r:    
                    s = nums[i] + nums[j] + nums[l]+ nums[r]

                    if s > target:
                        r -= 1
                    elif s < target:
                        l += 1
                    else:
                        solutions.append([nums[i], nums[j], nums[l], nums[r]])

                        while l<r and nums[l] == nums[l+1]:
                            l= l+1
                        while l<r and nums[r-1] == nums[r]:
                            r= r-1

                        l +=1
                        r -=1

        return solutions