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

링크

문제

이미 감소하지 않는 순서로 정렬된 1-indexed 배열 numbers이 주어졌을 때, 서로 더하여 target 이 되는 두 개의 수를 구합니다. 이 두 숫자를 numbers[index_1] 및 numbers[index_2]로 하고, 1 <= index1 < index2 < numbers.length로 합니다.

두 개의 숫자 index_1과 index_2를 원소로 갖는 정수 배열 [index1, index2]를 반환합니다.

테스트는 정확히 하나의 해가 나오도록 생성됩니다. 동일한 요소를 두 번 사용할 수 없습니다.

풀이

전형적인 투포인터, binary-search 문제이다.

class Solution {  
    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) {  
                break;  
            } else if (sum < target) {  
                left++;  
            } else {  
                right--;  
            }  
        }  
        return new int[]{left+1, right+1};  
    }  
}

메모리 사용량의 상위 %가 좋지 않길래 봤더니...

정답을 return 하기 전 gc를 하는 구질구질한 풀이들이 올라와 있었다.