[leetCode 167번] Two Sum II - Input Array Is Sorted (Java)

1. 문제

Two Sum II - Input Array Is Sorted - LeetCode

Two Sum II - Input Array Is Sorted - LeetCode

---

2. 문제설명

 

이 문제는 주어진 int 배열에서 두개를 더했을 때 target 값이 같을 경우 그 위치의 index를 반환하는 문제이다

 

(핵심) 이 문제의 핵심은 이미 정렬이 되어는 배열을 주어 진다는 점이다. 

 

---

3. 소스코드

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right){
            if(numbers[left] + numbers[right] > target ){
                right --;
            }else if (numbers[left] + numbers[right] < target){
                left++;
            }else{
                return new int[] {left+1 ,right+1};
            }
        }
        return null;
    }
}

 

---

4. 소스코드 해설

 

• 이 문제의 핵심은 이미 정렬이 된 배열을 주어 진다는 것이다. 
• 정렬이 되어있다면 two pointer 알고리즘을 사용하여 탐색을 하는 것이다 만약에 left + right 가 더 했을 때 target 값보다 클 경우에는 정렬된 오른쪽은 큰값이므로 right를 감소 한다.
• 반대로 left+right 가 target 값보다 작을경우 정렬되어 있어 left를 증가 시켜 값을 증가 시킨다.

---

5. 회고

 

만약 for문을 사용하여 이 문제를 푼다면 최악 O(N^2) 으로 이중 for문을 통해 반복 해야 한다. 하지만 TwoPointer를 사용한다면 한번의 반복으로 O(N)으로 줄 일 수 있다.