167. Two Sum II - Input Array Is Sorted

Two Sum과 Binary Search의 개념을 이용해서 풀 수 있는 간단한 문제

 

문제

 - 정렬된 배열에서 target이 되는 값을 찾아 index + 1 되는 배열을 return하기

 

해결방법

 - 배열이 이미 정렬되어 있어서 Binary Search를 사용

 

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

Binary Search는 중간 인덱스를 찾아서 계속 업데이트 해주는 방식인데 이 문제에서는 mid 대신 두 수의 합을 찾았다.

 

두 수의 합이 Target 보다 작을 때는 start 인덱스를 높여주면서 더 큰 합을 찾는다. 만약에 두 수의 합이 Target 보다 작으면 end 인덱스를 줄여주면서 합을 줄여 나가자.