[LeetCode/Java] 167. Two Sum II - Input Array Is Sorted

0. 문제

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

1. 문제 설명

• 오름차순으로 정렬된 정수 배열 numbers가 주어진다.
• numbers에서 두 원소의 합이 주어진 정수 target과 일치하는 한 쌍의 조합을 찾아라.
• target을 만족하는 원소 조합은 단 하나만 존재한다.

2. 문제 풀이

2.1. 접근법

• 투 포인터 알고리즘을 사용해서 원소 배열 양 끝 값을 비교한다.
• 두 포인터가 가리키는 원소의 값을 더한다.
• 합이 target보다 크면 오른쪽 포인터의 인덱스를 하나 낮춘다.
• 합이 target보다 작으면 왼쪽 포인터의 인덱스를 하나 높인다.

2.2. 의사코드

int 왼쪽 포인터 = 0;
int 오른쪽 포인터 = 배열 길이 - 1;

while (왼쪽 포인터 <= 오른쪽 포인터) {
    int sum = 배열[왼쪽 포인터] + 배열[오른쪽 포인터]
    
		if (sum이 target과 같으면) 정답 반환;

    else if (sum이 target보다 크면) 오른쪽 포인터를 - 1;
		else (sum이 target보다 작으면) 왼쪽 포인터를 + 1;
}

3. 코드

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int li = 0;
        int ri = numbers.length - 1;
        int[] ans = new int[2];
        
        while (li <= ri) {
            int sum = numbers[li] + numbers[ri];
            
            if (sum == target) {
                ans[0] = ++li;
                ans[1] = ++ri;
                break;
            }
            else if (sum > target) ri--;
            else li++;
        }
        return ans;
    }
}

4. 결과