[LeetCode][JAVA] 167. Two Sum II – Input Array Is Sorted

💡 문제

167. Two Sum II - Input Array Is Sorted

 (https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• 투 포인터(Two Pointers): 정렬된 배열의 양 끝에서 시작해 합계를 비교하며 포인터를 안쪽으로 이동.
• 단조성 활용: 배열이 오름차순 정렬(non-decreasing)이므로, 합이 작으면 왼쪽 포인터 증가, 크면 오른쪽 포인터 감소.

---

🤓 문제 풀이

정렬된 정수 배열 numbers(1-indexed)와 target이 주어질 때, 합이 target인 두 원소의 1-기반 인덱스를 반환한다.
배열이 정렬되어 있으므로 투 포인터로 O(n) 시간에 해결 가능하며, O(1) 공간만 사용한다.

 

🔨 문제 설명

• 입력
  • numbers: 정렬(오름차순)된 정수 배열 (길이 ≥ 2)
  • target: 정수
• 출력
  • [index1, index2] (1-indexed, index1 < index2)
  • 문제는 해가 유일하게 존재함을 보장

예)

• [2,7,11,15], 9 → [1,2]
• [2,3,4], 6 → [1,3]
• [-1,0], -1 → [1,2]

---

🔨 접근 방법

1. left = 0, right = n-1로 시작.
2. sum = numbers[left] + numbers[right]:
   • sum == target → 정답 반환(1-indexed로 변환).
   • sum < target → 합을 키워야 하므로 left++.
   • sum > target → 합을 줄여야 하므로 right--.
3. 유일 해 보장으로 루프 내에서 반드시 반환된다.

정렬 덕분에 “합이 작으면 왼쪽을 키운다 / 크면 오른쪽을 줄인다”는 단조적 이동이 가능.

---

🔨 문제 풀이 과정

 

• 시작: (left, right) = (0, n-1)
• 합 비교를 통해 한 번에 한 포인터만 이동 → right - left가 줄어들며 최대 n-1회 이동으로 종료
• 조건 충족 시 즉시 반환

 

 

---

🔨 구현코드

package leetcode;

/**
 * 167. Two Sum II - Input Array Is Sorted
 * 투포인터로 정렬된 배열에서 합 찾기
 * https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
 *
 * 이미 decre 순서가 아닌 순서로 정렬된 정수의 1-indexed 배열이 주어졌을 때,
 * 특정 목표 숫자에 합산되는 두 개의 숫자를 구합니다.
 * 이 두 숫자를 숫자[index1]과 숫자[index2]라고 하고, 여기서 숫자[index2]는 1 <= index1 < = numbers.length
 * 두 숫자, 인덱스1과 인덱스2의 인덱스를 길이 2의 정수 배열 [인덱스1, 인덱스2]로 하나씩 더한 값으로 반환
 * 테스트는 정확히 하나의 솔루션이 있도록 생성됩니다. 동일한 요소를 두 번 사용할 수 없습니다.
 * 솔루션은 일정한 여분의 공간만 사용해야 합니다.
 *
 *
 * 문제에서 “정답이 유일하게 존재”한다고 했으니 무한 루프 걱정 없이 반드시 반환.
 * 예 1:
 * 입력: 숫자 = [2,7,11,15], 대상 = 9
 * 출력: [1,2]
 * 설명: 2와 7의 합은 9입니다. 따라서 index1 = 1, index2 = 2. 우리는 [1, 2]를 반환합니다.
 *
 * 예제 2:
 * 입력: 숫자 = [2,3,4], 목표 = 6
 * 출력: [1,3]
 * 설명: 2와 4의 합은 6입니다. 따라서 인덱스1 = 1, 인덱스2 = 3. 우리는 [1, 3]을 반환합니다.
 *
 * 예제 3:
 * 입력: 숫자 = [-1,0], 목표 = -1
 * 출력: [1,2]
 * 설명: -1과 0의 합은 -1입니다. 따라서 인덱스1 = 1, 인덱스2 = 2. 우리는 [1, 2]를 반환합니다.
 *
 * 제약 조건:
 * 2 <= 숫자.길이 <= 3 * 104
 * -1000 <= 숫자 [i] <= 1000
 * 숫자는 decre가 아닌 순서대로 정렬됩니다.
 * -1000 <= 목표 <= 1000
 *
 * 시간: O(n) — 양 끝에서 한 번씩만 이동.
 *  두 포인터 left, right는 각각 단조롭게 한 방향으로만 이동
 *  매 반복에서 left++ 또는 right-- 중 하나가 수행되어 right - left가 최소 1씩 줄어들므로, 총 이동 횟수 ≤ n-1.
 * 공간: O(1) — 포인터 변수만 사용.
 *  포인터와 합계 등 상수 개의 보조 변수만 사용
 */
public class LeSolution03 {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1}; // 1-Indexed
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        LeSolution03 sol = new LeSolution03();
        System.out.println(sol.twoSum(new int[]{2, 7, 11, 15}, 9));
        System.out.println(sol.twoSum(new int[]{2,3,4}, 6));
        System.out.println(sol.twoSum(new int[]{-1,0}, -1));
        System.out.println(sol.twoSum(new int[]{1,2}, 3));
        System.out.println(sol.twoSum(new int[]{1,5,7,10}, 11));
        System.out.println(sol.twoSum(new int[]{5,5}, 10));
        System.out.println(sol.twoSum(new int[]{0,1,3,6}, 7));
        System.out.println(sol.twoSum(new int[]{-5,-3,0,2,8}, -8));
        System.out.println(sol.twoSum(new int[]{0,0,3,4}, 0));
        System.out.println(sol.twoSum(new int[]{1,2,4,6,10}, 8));
    }
}

---

📚 풀이 보완

코드 설명 (핵심 라인)

• sum == target → 정답 (1-indexed 반환)
• sum < target → 더 큰 합 필요 ⇒ left++
• sum > target → 더 작은 합 필요 ⇒ right--
• 0-indexed로 반환하는 실수: 반드시 +1 해주기.
• main에서 System.out.println(int[])을 그대로 출력 → 참조값 출력됨. Arrays.toString(...) 사용 필수.

엣지/중복 처리

• 같은 값이 중복되어도(예: [5,5], target=10) 투 포인터로 정확히 한 쌍을 찾음.
• 음수/0/양수 혼재도 동일 로직으로 처리 가능.

---

📍 Plus+

대안: 이진 탐색(O(n log n))

각 i에 대해 target - numbers[i]를 이진 탐색한다.

불변식

• 루프 진입 시 항상 left < right
• 이동은 항상 left++ 또는 right-- 중 하나만 수행 → 단조 감소하는 간격

시간 복잡도와 공간 복잡도 분석

 

시간 복잡도

공간 복잡도

요약

시간 복잡도: O(n)

• 포인터가 배열을 최대 한 번씩만 스캔

공간 복잡도: O(1)

• 추가 구조 없이 상수 변수만 사용

 

• 핵심 전략: 정렬 성질을 이용한 투 포인터
• 이점: O(n) 시간, O(1) 공간, 구현 간결
• 주의: 반환은 1-indexed

 

---

풀이 참고 로직

 

• sum == target → 정답
• sum < target → left++
• sum > target → right--