[리트코드] 18. 4Sum

728x90

문제 링크

4Sum - LeetCode

Can you solve this real interview question? 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] +

leetcode.com

문제 설명

제한사항

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

입출력 예

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]]

풀이 과정

정답

3중 for 문.

from collections import defaultdict
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        answer = set()

        n = len(nums)

        checked = defaultdict(bool)

        for a in range(n):
            for b in range(a+1, n):
                for c in range(b+1, n):
                    nums_d = target - nums[a] - nums[b] - nums[c]
                    if checked[nums_d] == True:
                        sub = sorted([nums[a], nums[b], nums[c], nums_d])
                        answer.add((sub[0], sub[1], sub[2], sub[3]))
                        
            checked[nums[a]] = True

        answer = list(answer)

        return answer