[리트코드] 18. 4Sum - python

18. 4Sum

문제

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:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

제한사항

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

풀이

3sum과 비슷하게 풀면 될 것 같은데 O (n^3)으로 풀면 될 것 같다고 생각했다.

이중 포문을 돌리면서 고정 인덱스 두개를 정하고 나머지 범위에서 포인터를 움직이면서 target 값과 mid 가 같은 곳을 찾는다. 조합을 찾아야하기 때문에 중복을 제거 해줘야한다.

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        answer = []
        
        for i in range(len(nums) - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
                
            for j in range(i + 1, len(nums) - 2):
                if j - 1 > i and nums[j] == nums[j - 1]:
                    continue
                l, r = j + 1, len(nums) - 1
                
                while l < r:
                    mid = nums[i] + nums[j] + nums[l] + nums[r]
                    
                    if mid < target:
                        l += 1
                    
                    elif mid > target:
                        r -= 1
                    else: # 하나 찾았으므로 중복 제거하고 다음 위치로
                        answer.append([nums[i] , nums[j] , nums[l] , nums[r]])
                        
                        while l < len(nums) - 1 and nums[l] == nums[l + 1]:
                            l += 1
                        
                        while r > 0 and nums[r] == nums[r - 1]:
                            r -= 1
                    
                        l += 1
                        r -= 1
    
        
        return answer