입력

1. 정수의 배열, 예: [1, 8, 15, 23]

2. 타겟 숫자, 예:16


출력

1. 합이 타겟 숫자가 되는 두 숫자의 배열 인덱스, 예: 0 2 (a[0]=1, a[2]=15, a[0]+a[2]=16)


조건

1. 각 입력은 정확히 1개의 해답을 가짐.

2. 두 숫자의 배열 인덱스는 서로 다른 값 (위의 예에서 a[1]+a[1] = 8+8 = 16이지만, 1 1은 인덱스가 같으므로 해답이 아님.)




이거.. 그냥 멍청하게 풀면 O(n^2) 나오는데 (a[0]에 대해 a[1]~a[n-1]까지 검사, a[1]에 대해 a[2]~a[n-1]까지 검사, 등등)


다양한 답이 존재함.


해시테이블 쓰는거. O(n)


입력을 정렬한 후 (O(n)), 인덱스 포인터 두 개 써서 앞 인덱스는 0부터 증가, 뒤 인덱스는 n-1부터 감소하면서 찾는법. O(n)


나도 이렇게 두 개는 생각해봤는데, 또다른 쌈박한 알고리즘이 있을까?


참고로, 저 문제를 일반화시키면 배열이 주어지고 k개의 서로 다른 인덱스에 있는 값들의 합이 타겟 숫자가 되는 k개의 인덱스를 찾아라 (중복 인덱스 불가). Two Sum은 쉬운데, Three Sum만 되도 O(n)은 쉽지 않을 것 같음. 왠지 Three Sum이면 O(n^2)가 최소일 것 같은데...


하여간, 오늘 릿코드 들어가서 문제 함 봤는데 1번 문제는 쉽네요. 코딩을 해볼 필요까지는 없을듯.