4Sum
정수 목록 nums와 정수 target이 주어집니다. 네 값이 nums의 서로 다른 네 위치에 있고 합이 target이 되는 모든 사중항 [a, b, c, d]를 반환하세요. 각 사중항의 값은 감소하지 않는 순서로 작성하세요. 서로 다른 위치에서 같은 네 값을 고를 수 있더라도 사중항은 한 번만 나타납니다. 첫 번째 값, 두 번째 값, 세 번째 값 순으로 답을 정렬하세요. 조건을 만족하는 사중항이 없으면 빈 목록을 반환하세요.
함수
- numsinteger-array
- 선택할 수 있는 숫자는 최소 하나
- targetinteger
- 각 4개 항의 합이 도달해야 하는 값
- 반환값integer-2d-array
- 합이 목표값인 서로 다른 네 원소 조합으로, 각 조합은 정렬되어 있고 목록도 정렬되어 있음; 해당 조합이 없으면 빈 목록
제약 조건
1 ≤ nums.length ≤ 200-108 ≤ nums[i] ≤ 108-109 ≤ target ≤ 109- 어떤 네 값의 합은
-4 × 108과4 × 108사이에 있으므로 32비트 정수에 들어갑니다. - 같은 네 값을 가진 네쌍둥이는 하나로 셉니다.
예제
- 입력
- nums = [3, -1, 0, 2, -2, 1, -3]target = 1
- 출력
- [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
- 설명
- 네 개의 사중항은 각각 합이 1입니다. 예를 들어
-3 + (-1) + 2 + 3입니다. -3으로 시작하는 두 항목은 두 번째 값에 따라 정렬되어 -1이 0보다 먼저 옵니다.
- 입력
- nums = [4, 4, 4, 4, 4, 4]target = 16
- 출력
- [[4, 4, 4, 4]]
- 설명
- 여섯 자리 중 네 자리를 선택하는 15가지 경우는 모두 4개의 4를 더해 16이 되므로,
[4, 4, 4, 4]는 한 번 나타납니다.
- 입력
- nums = [1, 5, 2, 9]target = 3
- 출력
- []
- 설명
- 유일한 선택지는 네 숫자 모두이며,
1 + 5 + 2 + 9 = 17이지 3이 아니므로 답은 빈 목록입니다.
후속 질문
서로 다른 네 수의 조합이 아니라, 값의 합이 target이 되는 네 위치의 조합 수를 세세요. 두 번째 예시에는 15개가 있습니다. O(n²)으로 할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
먼저 목록을 정렬하세요. 그러면 같은 값들이 나란히 놓이고, 왼쪽에서 오른쪽으로 선택한 네 값은 비내림차순으로 정렬됩니다.
처음 두 값인
nums[i]와nums[j]를 고정합니다. 여기서i < j입니다. 그러면j의 오른쪽에 있는 정렬된 값들 중에서target - nums[i] - nums[j]의 합이 되어야 하는 한 쌍이 남습니다. 이는 정렬된 목록에서의 Two Sum입니다.두 개의 포인터로 쌍을 찾습니다.
lo는j바로 다음에,hi는 마지막 인덱스에 둡니다. 목표값보다 작으면lo를 오른쪽으로 이동하고, 크면hi를 왼쪽으로 이동합니다. 반복문에서 마지막으로 확인한 값과 같은 값을 가진i또는j는 건너뛰고, 일치하는 값을 찾은 뒤에는 값이 달라질 때까지lo를 계속 이동합니다.
풀이
네 위치의 모든 조합을 확인하면 O(n⁴)의 비용이 들고, 중복 값 때문에 같은 네 쌍이 여러 번 만들어집니다. 3Sum 축소를 한 단계 더 적용하세요. 정렬한 다음, 두 개의 반복문으로 처음 두 값을 고정하고, 투 포인터로 마지막 쌍을 찾은 뒤, 각 단계에서 중복 값을 건너뛰세요.
네 개씩 이루어진 모든 조합을 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
먼저 정렬하면 i < j < k < l 위치의 값이 비내림차순이 되고 각 4개 값의 조합이 올바른 순서로 출력됩니다. 중첩된 네 개의 루프는 가능한 네 위치의 모든 조합을 탐색합니다. 중복을 피하기 위해 다음 위치의 값이 한 단계 앞에서 시도한 값과 같으면 루프가 다음으로 넘어갑니다. 4가 여섯 개 있을 때는 각 루프가 첫 번째 위치만 시도하므로 [4, 4, 4, 4]가 15번이 아니라 한 번 출력됩니다.
숫자 200개에서는 네 개씩 묶는 조합이 64,684,950개이며, n이 두 배가 되면 그 수는 약 16배로 늘어납니다.
알고리즘
nums를 정렬합니다.i < j < k < l에 대한 네 개의 루프를 중첩하고, 각 루프는 바깥 루프의 시작 위치보다 하나 뒤에서 시작합니다.- 각 루프에서 첫 번째 위치가 아니면서 바로 앞 위치와 같은 값을 가진 위치는 건너뜁니다.
- 네 값의 합이
target과 같으면[nums[i], nums[j], nums[k], nums[l]]을 기록합니다. 루프는 이들을 정렬된 순서로 생성합니다.
def fourSum(nums, target):
nums = sorted(nums)
n = len(nums)
quads = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue # same first value as the round before
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # same second value as the round before
for k in range(j + 1, n - 1):
if k > j + 1 and nums[k] == nums[k - 1]:
continue # same third value as the round before
for l in range(k + 1, n):
if l > k + 1 and nums[l] == nums[l - 1]:
continue # same fourth value as the round before
if nums[i] + nums[j] + nums[k] + nums[l] == target:
quads.append([nums[i], nums[j], nums[k], nums[l]])
return quads정렬, 두 개의 루프, 두 개의 포인터
핵심 아이디어
nums[i]와 nums[j]를 고정하면, 남는 것은 두 수의 합을 찾는 문제입니다. j 오른쪽에 있는 두 값의 합이 target - nums[i] - nums[j]가 되도록 찾으면 됩니다. 정렬된 목록에서는 한 번 훑는 것으로 답을 찾을 수 있습니다. lo는 j+1로, hi는 마지막 인덱스로 설정합니다. 합이 target보다 작으면 lo를 오른쪽으로 옮기고, 합이 더 크면 hi를 왼쪽으로 옮깁니다.
이동할 때마다 정답에 포함될 수 없는 값 하나를 제외합니다. 합이 너무 작다면, 남은 가장 큰 값인 nums[hi]도 nums[lo]와 더했을 때 충분하지 않으므로 nums[lo]를 제외할 수 있습니다. 합이 너무 큰 경우에는 반대 이유로 nums[hi]를 제외합니다. 하나의 쌍 (i, j)에는 최대 n번의 이동이 필요하므로, n²/2개의 쌍에 대해 총 O(n³)의 비용이 듭니다.
첫 번째 예시에서 i가 -3을, j가 -1을 가리킬 때, lo는 0에서 1을 지나 2까지 이동합니다. 이때 -3 + (-1) + 2 + 3 = 1입니다.
알고리즘
nums를 정렬합니다.- 각
i에 대해,i > 0이고nums[i]가nums[i-1]과 같으면 건너뜁니다. i다음의 각j에 대해,j > i+1이고nums[j]가nums[j-1]과 같으면 건너뜁니다.lo = j+1과hi = n-1로 설정합니다.lo < hi인 동안 네 값의 합을target과 비교합니다. 합이 더 작으면lo를 오른쪽으로 이동하고, 더 크면hi를 왼쪽으로 이동합니다.- 일치하면 네 수의 조합을 기록하고 두 포인터를 모두 이동한 다음,
lo가 방금 사용한 값을 가리키는 동안lo를 계속 이동합니다.
def fourSum(nums, target):
nums = sorted(nums)
n = len(nums)
quads = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue # this first value was already handled
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # this second value was already handled
lo, hi = j + 1, n - 1
while lo < hi:
total = nums[i] + nums[j] + nums[lo] + nums[hi]
if total < target:
lo += 1
elif total > target:
hi -= 1
else:
quads.append([nums[i], nums[j], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
return quads
함정과 경계 사례
nums[j]가nums[j-1]와 같을 때j를 건너뜁니다.j = i+1일 때는i에서 사용하는 값과 비교하므로, target이 8일 때[2, 2, 2, 2, 2]에서[2, 2, 2, 2]를 놓치게 됩니다.- 3Sum의 조기 종료 조건인
nums[i] > target을 그대로 복사합니다.[-5, -4, -3, -2, -1]에서 target이 -10이면 루프가 -5에서 멈춰[-4, -3, -2, -1]을 놓칩니다. - 길이가 4보다 짧은 목록입니다. 숫자가 한 개나 두 개일 때
n-3은 음수가 됩니다. Swift에서는0..<(n - 3)이 트랩을 발생시키고, Rust의usize에서n - 3은 언더플로가 발생합니다. 먼저 빈 목록을 반환하세요. - 사중항을 해시 집합에 모은 뒤 정렬하지 않은 상태로 반환합니다.
자주 묻는 질문3
4Sum의 시간 복잡도는 무엇인가요?
O(n³). 두 루프는 약 n²/2개의 쌍 (i, j)을 선택하고, 각 쌍마다 최대 n단계의 투 포인터 탐색을 한 번 수행합니다. O(n log n) 정렬은 이에 비하면 작은 비용입니다.
4Sum을 kSum으로 어떻게 일반화할까요?
정렬된 리스트에서 kSum(nums, target, k)을 작성하세요. k = 2일 때는 두 포인터 순회를 실행합니다. k가 더 크면 첫 번째 값을 반복해서 순회하고 중복을 건너뛴 다음, 오른쪽에 있는 값들에 대해 k-1과 target - nums[i]를 사용해 자기 자신을 호출합니다. 각 단계에서 n이라는 인자가 추가되므로 kSum의 시간 복잡도는 O(n^(k-1))입니다.
4Sum을 O(n²)에 풀 수 있을까요?
n²/2개의 쌍의 합을 해시 맵에 그룹화하고 각 쌍을 자신의 합을 target에서 뺀 값과 같은 합을 갖는 쌍과 짝지을 수 있습니다. 합을 공유하는 쌍이 적을 때는 빠르지만, 하나의 합에 O(n²)개의 쌍이 들어갈 수 있으므로 최악의 경우에도 O(n³)보다 나을 것이 없습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def fourSum(nums, target):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
nums = [3, -1, 0, 2, -2, 1, -3] target = 1
예상 출력
[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]