3Sum

먼저 목록을 정렬하세요. 그러면 임의의 세 위치 i < j < k에 있는 값은 이미 순서대로 배치되어 있으므로 nums[i] ≤ nums[j] ≤ nums[k], 트리플릿을 찾는 즉시 올바르게 작성됩니다. 중첩된 세 개의 반복문은 모든 위치 조합을 방문하므로 어떤 트리플릿도 놓치지 않습니다.

다음은 중복입니다. 첫 번째 예제를 정렬하면 [-2, -1, 0, 1, 1, 2]이고, [-1, 0, 1]의 1은 인덱스 3이나 인덱스 4에서 가져올 수 있습니다. 따라서 각 반복문은 같은 반복문에서 이전에 시도한 값과 같은 값을 가진 위치를 건너뜁니다. 그러면 각 반복문은 서로 다른 값을 각각 한 번씩 시도하고, 서로 다른 각 트리플릿은 정렬된 상태로 한 번씩만 나옵니다. 건너뛰기는 같은 반복문 안의 이전 위치와만 비교하므로 [-2, 1, 1]에서는 여전히 두 개의 1을 모두 사용합니다.

문제는 비용입니다. 트리플릿은 약 n³/6개이므로, 숫자 3000개라면 합계를 4.5 × 10^9번 계산해야 하며, 이는 어떤 시간 제한도 훨씬 초과합니다.

첫 번째 값 nums[i]를 고정하면, 합이 -nums[i]가 되는 뒤쪽 값 두 개가 필요합니다. 이것이 Two Sum입니다. j를 i의 오른쪽으로 이동시키고, 지나온 값들을 집합에 저장합니다. 각 j에서 필요한 값은 need = -nums[i] - nums[j]입니다. need가 집합에 있으면 [nums[i], need, nums[j]]의 합은 0입니다. 집합 조회는 평균적으로 O(1)이 걸리므로, 하나의 i에 O(n), 전체 탐색에는 O(n²)이 걸립니다.

정렬은 여전히 중복 처리를 도와줍니다. 값이 바로 앞의 값과 같은 i는 건너뜁니다. 일치하는 값을 찾은 뒤에는 j를 nums[j]의 모든 복사본을 지나도록 이동합니다. 첫 번째 값과 세 번째 값이 고정되면 가운데 값도 고정되므로, 같은 값이 또 나오면 동일한 세 수 조합만 반복됩니다. need는 정렬된 목록에서 더 앞선 위치의 값이므로 need ≤ nums[j]이고, 세 수 조합은 순서대로 정렬됩니다. 또한 nums[i] > 0이 되는 즉시 탐색을 중단할 수 있습니다. 그 뒤의 두 값은 이 값보다 크거나 같으므로 합이 0이 될 수 없습니다.

한 가지 세부 사항이 있습니다. j가 오른쪽으로 이동하면 nums[j]는 커지고 need는 작아지므로, 하나의 i에 대한 세 수 조합은 가운데 값이 감소하는 순서로 나옵니다. [-2, -1, 0, 1, 1, 2]에서 i = 0일 때 두 번째 1에서 [-2, 1, 1]을 찾고, 그다음 2에서 [-2, 0, 2]를 찾습니다. 각 그룹을 답에 추가하기 전에 뒤집으세요. C 및 R 버전은 해시 집합 대신 값으로 인덱싱된 배열에 확인한 값을 표시합니다. 모든 값이 ±10^5 범위에 있으므로 이렇게 할 수 있습니다.

정렬된 순서로 집합을 대체할 수 있습니다. nums[i]를 고정하고, lo를 i+1에, hi를 마지막 인덱스에 둔 다음 nums[i] + nums[lo] + nums[hi]를 살펴봅니다. 합이 0보다 작으면 더 큰 값이 필요하므로 lo를 오른쪽으로 이동합니다. 0보다 크면 더 작은 값이 필요하므로 hi를 왼쪽으로 이동합니다. 정확히 0이면 세 값의 조합을 기록하고 두 포인터를 모두 이동합니다.

어떤 세 값의 조합도 놓치지 않습니다. 합이 0보다 작을 때는 남은 값 중 가장 큰 값인 nums[hi]와 더해도 nums[lo]가 부족하므로, 현재 범위에 남아 있는 어떤 값과도 짝을 이룰 수 없습니다. 따라서 이 값을 버려도 아무것도 잃지 않습니다. 0보다 큰 경우는 그 반대입니다. 남은 값 중 가장 작은 값과 더해도 nums[hi]가 너무 큽니다. 매 단계마다 값 하나를 영구적으로 제외하므로, i 하나당 최대 n번의 단계가 필요하고 전체 탐색은 O(n²)이며, 정렬과 결과 출력 외에는 메모리가 필요하지 않습니다.

정렬된 [-2, -1, 0, 1, 1, 2]를 살펴보겠습니다. i = 0일 때(값은 -2), lo는 -1에서 시작하고 hi는 2에서 시작합니다. 합은 -1이므로 lo를 0으로 이동합니다. 이제 -2 + 0 + 2 = 0이므로 [-2, 0, 2]를 기록하고, 두 포인터는 1 두 개가 있는 위치에 도달합니다. 이 값들로 [-2, 1, 1]을 얻습니다. i = 1일 때(값은 -1), 0과 2의 합은 1이므로 hi를 두 번째 1로 이동하고, -1 + 0 + 1 = 0이 되어 [-1, 0, 1]을 기록합니다. i = 2의 값 0으로는 아무것도 찾지 못하고, i = 3에서는 값이 양수이므로 탐색을 중단합니다.

중복 값은 두 가지 규칙으로 처리해야 합니다. 값이 바로 앞의 값과 같은 i는 건너뜁니다. 일치하는 값을 찾은 후에는 lo를 사용한 값의 중복 항목들을 지나 이동합니다. hi에는 별도의 규칙이 필요하지 않습니다. lo가 더 큰 값에 놓이면, 이전 nums[hi]의 중복 값은 이제 합을 0보다 크게 만들고 저절로 제외됩니다. i가 서로 다른 값들을 오름차순으로 방문하고 lo는 오른쪽으로만 이동하므로, 세 값의 조합도 정렬된 순서로 나옵니다.