18. 4Sum

Description

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.

Example 1:

• Input: nums = [1,0,-1,0,-2,2], target = 0
• Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

• Input: nums = [2,2,2,2,2], target = 8
• Output: [[2,2,2,2]]

Constraints:

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

Submitted Code

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        result = []

        for i in range(n-3):            # 1번째 숫자 고정
            if i > 0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1, n-2):   # 2번째 숫자 고정
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                l = j+1                 # 3번째 숫자 포인터(왼쪽)
                r = n-1                 # 4번째 숫자 포인터(오른쪽)

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

Runtime: 384 ms | Beats 71.43%
Memory: 19.30 MB | Beats 95.42%

15. 3Sum 문제를 확장해서 2개의 숫자를 고정하고 나머지 숫자 2개는 포인터 2개로 탐색했다.

Other Solutions

1st

class Solution:  # 1084 ms, faster than 37.26%
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def dfs(l, r, k, target, path, out):  # [l, r] inclusive
            if k == 2:   # 종료조건
                while l < r:
                    if nums[l] + nums[r] == target:
                        out.append(path + [nums[l], nums[r]])
                        while l+1 < r and nums[l] == nums[l+1]: l += 1  # Skip duplicate nums[l]
                        l, r = l + 1, r - 1
                    elif nums[l] + nums[r] > target:
                        r -= 1  # Decrease sum
                    else:
                        l += 1  # Increase sum
                return

            while l < r:
                dfs(l+1, r, k - 1, target - nums[l], path + [nums[l]], out)
                while l+1 < r and nums[l] == nums[l+1]: l += 1  # Skip duplicate nums[i]
                l += 1

        def kSum(k):  # k >= 2
            ans = []
            nums.sort()
            dfs(0, len(nums)-1, k, target, [], ans)
            return ans

        return kSum(4)

time complexity: 𝑂(𝑛^k-1)
space complexity: 𝑂(𝑛)

kSum에 사용할 수 있는 일반화 방식으로, k에서 1씩 줄여가며 재귀호출 하다가 마지막 2Sum이 됐을 때 two-pointer로 해결하면 된다.