[Two Pointers][Medium] 167. Two Sum II - Input Array is Sorted.

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

 

Q. 오름차순 정렬된 정수배열 numbers가 주어질 때, 두 수의 합이 target이 되는 두 index를 찾아라. 

 

 

Solution. 

 정렬된 배열이 주어지면, 대다수 검색 방법이 정해져 있다. 

 

 Binary Search를 사용하도록 한다. 

 

 어떤 대상에 대해? 

 현재 값과 그 합이 target이 되는 수를 검색하면 된다. 

 

 코드를 작성해 본다. 

int findNum(int[] numbers, int target, int left, int right)
{
    if(left > right)    return -1;

    int mid = left + (right-left) / 2;
    if(numbers[mid] == target)     return mid;
    else if(numbers[mid] > target)  return findNum(numbers, target, left, mid-1);
    else return findNum(numbers, target, mid+1, right);
}

public int[] TwoSum(int[] numbers, int target) 
{
    HashSet<int> dataSet = new HashSet<int>();
    for(int k = 0; k < numbers.Length; ++k)
    {
        int idx = findNum(numbers, target-numbers[k], k+1, numbers.Length-1);
        if(idx > -1)
            return new int[]{k+1, idx+1};
    }
    return new int[]{-1, -1};
}

 

그닥 특별할 것이 없다. 

 

 

결과.