투포인터 - 정렬된 배열에서 두 수의 합

Note

정렬된 배열에서 두 원소의 합이 목표값이 되는 인덱스를 찾을 때, 왼쪽·오른쪽 포인터를 이동시키며 O(n)에 해결하는 원리입니다.

---

문제 상황

• 배열: 비감소 순으로 정렬된 numbers
• 목표: numbers[i] + numbers[j] = target 인 (i, j) 찾기 (i < j)
• 조건: 정답은 유일하고, 추가 공간 O(1) 만 사용

정렬이 되어 있지 않다면 해시로 O(n)에 풀 수 있지만, 정렬이 보장되면 투포인터로 같은 시간에 상수 공간만 쓰며 풀 수 있습니다.

---

왜 투포인터인가?

정렬의 활용

배열이 비감소이므로:

• 왼쪽에 가까울수록 값이 작고
• 오른쪽에 가까울수록 값이 큽니다.

그래서 맨 왼쪽과 맨 오른쪽에서 시작해,
합이 target보다 작으면 왼쪽을 오른쪽으로, 크면 오른쪽을 왼쪽으로 옮기면 됩니다.

포인터 이동의 의미

• left: 더해지는 두 수 중 작은 쪽 후보
• right: 큰 쪽 후보

합 vs target	의미	조치
sum < target	작은 수가 너무 작음	left += 1 (더 큰 수로)
sum > target	큰 수가 너무 큼	right -= 1 (더 작은 수로)
sum == target	정답	[left+1, right+1] 반환

---

알고리즘 설계

초기화

• left = 0, right = len(numbers) - 1

반복

1. two_sum = numbers[left] + numbers[right]
2. two_sum == target → [left+1, right+1] 반환 (1-indexed)
3. two_sum < target → left += 1
4. two_sum > target → right -= 1
5. left < right 인 동안만 반복 (같은 원소 두 번 쓰지 않음)

종료

• 정답이 유일하다고 보장되므로, 반복 안에서 반드시 한 번은 two_sum == target 이 됩니다.

---

왜 다른 조합을 놓치지 않나?

• left를 키우면: 같은 right에 대해 합이 증가
• right를 줄이면: 같은 left에 대해 합이 감소

그래서:

• 합이 작을 때는 left만 키우고,
• 합이 클 때는 right만 줄이면,

현재 (left, right)보다 작은 left나 큰 right 조합은 더 이상 정답이 될 수 없습니다.
따라서 한 번에 한 방향으로만 범위를 줄여도 정답을 놓치지 않습니다.

---

예시: numbers = [2, 7, 11, 15], target = 9

left	right	numbers[left]	numbers[right]	sum	동작
0	3	2	15	17	17 > 9 → right -= 1
0	2	2	11	13	13 > 9 → right -= 1
0	1	2	7	9	9 == 9 → [1, 2] 반환

---

시간·공간 복잡도

• 시간: O(n) — left는 증가, right는 감소만 하므로 최대 2n번 연산
• 공간: O(1) — 포인터 두 개만 사용

---

관련 문제

• LeetCode 167: Two Sum II - Input Array Is Sorted - 코드 구조 설명