주어진 합을 만드는 쌍 찾기

배열과 목표값이 주어졌을 때, 두 값을 add하여 목표값을 만드는 쌍을 찾으십시오. 대회에서 가장 흔한 입문 문제 중 하나입니다. 🔍

가장 단순한 방법은 중첩 반복문 두 개로 모든 쌍을 시도하는 것입니다. 동작은 하지만 모든 쌍을 확인하는 데 O(n^2)이 걸려 너무 느릴 수 있습니다.

n이 100000에 가까우면 O(n^2)은 100억 번의 검사이며 TLE가 발생합니다. 제한 조건은 더 빠른 방법을 찾으라고 알려 주고 있습니다.

먼저 배열을 sort하면 양끝의 두 포인터로 한 번의 순회에 문제를 해결할 수 있습니다. 정렬에 O(n log n)이 걸리고, 그다음 순회에는 O(n)이 걸립니다.

각 단계에서 a[left] + a[right]를 확인하십시오. 이 하나의 값이 추측 없이 다음 이동을 결정합니다.

합이 목표값과 같으면 쌍을 찾은 것입니다. 유효한 답 하나만 필요하므로 즉시 반환하십시오.

합이 너무 작으면 왼쪽 포인터를 오른쪽으로 이동하고, 너무 크면 오른쪽 포인터를 왼쪽으로 이동하십시오. 정렬된 순서가 각 이동이 도움이 된다는 것을 보장합니다.

일치하는 값 없이 포인터가 서로 지나치면 유효한 쌍이 존재하지 않습니다. 반복문이 끝나는 것 자체가 완전한 답입니다.

원래 인덱스를 유지해야 한다면 해시 집합이 더 깔끔합니다. 각 값에 대해 목표값에서 그 값을 뺀 값이 이미 등장했는지 확인하십시오.

배열이 정렬되어 있거나 정렬할 수 있다면 두 포인터를 사용하십시오. 정렬하지 않고 정확히 O(n)을 달성해야 하거나 인덱스를 유지해야 한다면 해시 집합을 사용하십시오.

어떤 값이 자기 자신과 짝을 이룰 수 있다면 두 인덱스가 서로 달라야 합니다. 간단히 left != right 또는 i != j인지 확인하면 이 함정을 피할 수 있습니다.

목표값이 되는 쌍을 찾을 때 O(n^2) 완전 탐색보다 빠른 방법을 원합니다.

두 포인터로 정렬한 뒤 훑으면 O(n log n)에 목표 쌍을 찾을 수 있고, 인덱스가 중요할 때는 해시 집합으로 O(n)에 해결할 수 있습니다. 제한 조건에 따라 선택하십시오. ✅