Two Sum
정수 배열 nums와 정수 target이 주어집니다. nums의 서로 다른 두 위치에 있는 정확히 두 항목의 합이 target이 됩니다. 이 두 항목의 인덱스를 반환하세요. 작은 인덱스를 먼저 반환합니다.
함수
- numsinteger-array
- 검색할 정수 배열
- targetinteger
- 두 항목의 합이 도달해야 하는 값
- 반환값integer-array
- 두 인덱스 중 더 작은 것이 먼저
제약 조건
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- 서로 다른 위치의 쌍은 정확히 하나이며, 그 합은
target입니다.
예제
- 입력
- nums = [3, 8, 12, 5]target = 17
- 출력
- [2, 3]
- 설명
- 12는 인덱스 2에 있고 5는 인덱스 3에 있으며, 12 + 5 = 17입니다. 다른 어떤 쌍도 17에 도달하지 않습니다.
- 입력
- nums = [6, 1, 4, 10]target = 7
- 출력
- [0, 1]
- 설명
- 인덱스 0의 6과 인덱스 1의 1을 더하면 7이 됩니다. 이 쌍이 처음 두 항목일 수 있습니다.
- 입력
- nums = [2, -6, 9, 4, 13]target = 3
- 출력
- [1, 2]
- 설명
- 인덱스 1의 -6과 인덱스 2의 9를 더하면 3이 됩니다. 음수도 양수와 같은 방식으로 짝을 이룹니다.
후속 질문
만약 nums가 이미 정렬된 상태로 주어진다면, 추가 메모리를 O(1)만 사용하여 O(n) 시간에 쌍을 찾을 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
두 개의 중첩 루프로 모든 쌍을 확인하면 올바르지만, 숫자가 10,000개라면 약 5천만 번 확인해야 합니다. 목록을 다시 훑지 않고 각 숫자의 짝을 찾을 수 있을까요?
값
x에 서 있으면 쌍을 완성할 값, 즉 목표값에서x를 뺀 값이 무엇인지 이미 알고 있습니다. 남은 질문은 그 값을 이전에 지나쳤는지, 그리고 어느 인덱스에 있는지입니다.목록을 한 번 순회하면서 지금까지 지나온 각 값과 그 인덱스를 해시 맵에 저장하세요. 각 위치에서 먼저 짝이 되는 값을 찾으세요. 그 값이 맵에 있으면 두 인덱스를 모두 찾은 것입니다. 그렇지 않으면 현재 값을 저장하고 다음으로 넘어가세요. 저장하기 전에 찾으면 숫자가 자기 자신과 짝을 이루는 것을 막을 수 있습니다.
풀이
모든 쌍을 확인하는 방법도 통하지만, 길이의 제곱에 비례해 작업량이 늘어납니다. 질문을 뒤집어 봅시다. 숫자 x에 서 있다고 할 때, 짝이 되는 숫자는 target - x라는 것을 이미 알고 있습니다. 해시 맵을 사용하면 해당 값을 이미 지나쳤는지 상수 시간에 확인할 수 있으므로 한 번만 순회하면 충분합니다.
모든 쌍 확인하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
첫 번째 인덱스 i를 고정하고, nums[i] + nums[j]가 target과 같아질 때까지 오른쪽의 모든 인덱스 j를 시도합니다. j를 i + 1에서 시작하면 한 위치가 자기 자신과 짝을 이루는 것을 방지하고, 각 쌍을 한 번씩만 시도하며, 더 작은 인덱스를 앞에 둡니다. 원하는 쌍도 시도하는 쌍 중 하나이므로 찾을 수 있습니다.
n개의 숫자는 약 n²/2개의 쌍을 이룹니다. n = 10^4이면 덧셈이 약 5 × 10^7번 이루어집니다.
알고리즘
nums의 모든 인덱스에 대해i를 반복합니다.- 각
i에 대해j를i + 1부터 마지막 인덱스까지 반복합니다. nums[i] + nums[j]가target과 같으면[i, j]를 반환합니다.- 두 반복문이 모두 끝나면 빈 배열을 반환합니다. 문제에서 이런 일은 절대 발생하지 않는다고 보장합니다.
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []해시 맵을 사용한 한 번의 순회
핵심 아이디어
고정된 nums[i]에 대해 브루트 포스의 내부 루프는 미리 알고 있는 값 하나, 즉 target - nums[i]를 찾습니다. 이 탐색은 사실상 조회 작업이며, 값에서 인덱스로 매핑하는 해시 맵을 사용하면 평균적으로 상수 시간에 조회할 수 있습니다.
먼저 조회하고, 그다음 저장하세요. 그러면 숫자는 자기 자신이 아니라 그 앞에 있는 숫자와만 짝을 이룰 수 있고, 짝이 되는 숫자는 항상 앞에 있으므로 그 인덱스가 먼저 옵니다. 각 숫자를 한 번씩 방문하고 맵 연산은 상수 시간이므로 탐색은 O(n)입니다. 그 대가로 최대 n개의 항목을 저장하는 맵이 필요합니다.
알고리즘
- 값을 인덱스에 매핑하는 빈 맵을 만듭니다.
- 각 인덱스
i에 대해 쌍을 완성하는 값인need를 계산합니다.target에서nums[i]를 뺀 값입니다. need가 맵에 있으면 저장된 인덱스와i를 차례로 반환합니다.- 그렇지 않으면
nums[i]를 인덱스i와 함께 저장하고 계속합니다.
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
함정과 경계 사례
- 짝을 찾기 전에 숫자를 저장하는 것.
[4, 2, 6]과target = 8의 경우, 4가 자기 자신을 찾아[0, 0]을 반환합니다. - 잘못된 순서로 인덱스를 반환하는 것. 조회한 다음 저장하면, 맵의 인덱스가 더 작은 값이므로 먼저 옵니다.
- 투 포인터를 사용하려고 배열을 정렬한 다음, 정렬된 복사본에서 위치를 반환하는 것. 각 값의 원래 인덱스를 값 옆에 유지하세요.
- 값이 양수이거나 서로 다르다고 가정하는 것.
target = 0일 때[0, 7, -3, 0]은 두 개의 0을 짝지어[0, 3]을 반환합니다. - Lua와 R에서 1부터 시작하는 인덱스를 반환하는 것. 각각에서 1을 빼세요.
자주 묻는 질문3
Two Sum의 시간 복잡도는 얼마인가요?
해시 맵 솔루션은 각 숫자를 한 번씩 방문하고 각 조회 또는 삽입이 평균적으로 상수 시간에 이루어지므로 O(n) 시간이 걸립니다. 맵에 O(n)의 추가 공간을 사용합니다. 모든 쌍을 확인하면 O(n²) 시간이 걸리고 O(1) 공간을 사용합니다.
추가 공간 없이 Two Sum을 풀 수 있을까요?
정렬되지 않은 배열에서는 선형 시간으로 처리할 수 없습니다. 추가 공간을 O(1)로 제한하면 모든 쌍을 다시 확인해야 하며, 이는 O(n²)입니다. 해시 맵은 선형 시간을 얻는 대신 O(n)의 메모리를 사용합니다.
Two Sum은 중복된 숫자를 어떻게 처리하나요?
현재 숫자를 저장하기 전에 짝을 찾으면 중복된 값도 처리할 수 있습니다. [7, 3, 7]에서 target = 14인 경우, 첫 번째 7은 인덱스 0에 저장되고 두 번째 7은 첫 번째 7을 찾아 [0, 2]를 반환합니다. 7 하나만으로는 자기 자신과 짝을 이루지 않습니다. 7을 찾을 때 아직 맵에 저장되어 있지 않기 때문입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def twoSum(nums, target):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
nums = [3, 8, 12, 5] target = 17
예상 출력
[2, 3]