← 8주차 · 투 포인터와 슬라이딩 윈도우
쉬움투 포인터배열

정렬된 배열의 두 수의 합

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어져요. 더해서 target이 되는 두 원소의 인덱스를 오름차순 배열 [i, j]로 반환해요.

정답은 항상 정확히 하나 있고, 같은 원소를 두 번 쓸 수 없어요. 배열이 정렬돼 있다는 점을 이용해 해시 없이 O(n), 추가 메모리 없이 푸는 것이 목표예요.

예시

예시 1
입력
nums = [2, 7, 11, 15], target = 9
출력
[0, 1]
설명
nums[0] + nums[1] = 2 + 7 = 9.
예시 2
입력
nums = [1, 3, 4, 5, 7, 11], target = 15
출력
[2, 5]
설명
nums[2] + nums[5] = 4 + 11 = 15.

제한 사항

  • 2 ≤ nums.length ≤ 100,000
  • nums는 오름차순으로 정렬돼 있어요.
  • -10^9 ≤ nums[i], target ≤ 10^9
  • 정답은 유일하게 있어요.
양끝에서 포인터 둘을 시작해요. 두 값의 합이 target보다 작으면 왼쪽을 오른쪽으로 한 칸(더 큰 값), 크면 오른쪽을 왼쪽으로 한 칸(더 작은 값) 옮겨요. 정렬돼 있어서 이 방향 판단이 항상 옳아요.
javascript
function twoSumSorted(nums, target) {
  let i = 0;
  let j = nums.length - 1;
  while (i < j) {
    const sum = nums[i] + nums[j];
    if (sum === target) return [i, j];
    if (sum < target) i++;
    else j--;
  }
  return [];
}
이전 문제애너그램 묶기
다음 문제정렬된 배열 중복 제거
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.