[릿코드] 167번 : Two Sum II - Input array is sorted

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

Two Sum II - Input array is sorted - LeetCode

---

 

문제

오름차순의 정수 배열이 주어진다. 합해서 target 숫자가 되는 두개의 숫자를 찾아서 인덱스를 리턴해라.

단, 항상 하나의 답이 있으며 같은 인덱스를 두번 더해선 안된다.

 

어떻게 풀까

for문 두개를 사용한다. 

첫번째 포문 안에선 순서대로 value를 읽는다.

두번째 포문 안에선 target-value를 찾는데, 이때 binary search를 사용한다.

 

구현

 

 

class Solution {

    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[]{};
        for(int i=0;i<numbers.length;i++) {
            int value = numbers[i];
            int tmpTarget = target - value;
            int targetIdx = findTarget(i+1, numbers, tmpTarget);
            if(targetIdx != -1) {
                result = new int[]{i + 1, targetIdx + 1};
                break;
            }
        }
        return result;
    }

    private int findTarget(int leftIdx, int[] numbers, int target) {
        int rightIdx = numbers.length - 1;
        int result = -1;
        while(rightIdx >= leftIdx) {
            int midIdx = (rightIdx + leftIdx) / 2;
            int mid = numbers[midIdx];
            if (mid == target) return midIdx;
            if (mid > target) {
                rightIdx = midIdx - 1;
            } else if (mid < target) {
                leftIdx = midIdx + 1;
            }
        }
        return result;
    }
}