167. Two Sum II

문제 링크: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

지난 번 작성한 Two Sum을 다르게 풀어보는 문제이다.
input으론 정렬된 배열이 주어지고, 합이 target이 되는 두 원소를 찾아 그 위치를 반환하는 문제이다.

Solution

1. existing Solution

• Two Sum의 Brute Force Solution으로는 O(N^2)의 시간, O(1)의 공간 복잡도로 문제를 해결할 수 있다.
• Two Sum의 HashMap Solution으로는 O(N)의 시간, O(N)의 공간 복잡도로 문제를 해결할 수 있다.

하지만, 위의 두 해결방법은 input으로 주어진 배열이 정렬된 상태라는 것을 활용하지 않는다.
이를 활용해 더 나은 방법으로 문제를 풀어볼 수 있다.

2. Two-Pointer Approach

각각 정렬된 배열의 첫번째 원소와 마지막 원소를 가리키고 있는 두 index를 사용할 것이다.
두 포인터가 가리키는 위치의 두 원소의 합과 target을 비교한다.

• 만약 합이 target과 같다면, 바로 그 위치를 반환한다.
• 만약 그 합이 target보다 작다면, 더 작은 원소를 가리키고 있는 왼쪽 index를 오른쪽으로 한 칸 이동한다.
• 만약 그 합이 target보다 크다면, 더 큰 원소를 가리키고 있는 오른쪽 index를 왼쪽으로 한 칸 이동한다.
  두 index를 이동하면서 solution을 발견할 때까지 iteration을 반복한다.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int lo=0;
        int hi=numbers.length-1;
        int sum;
        while(lo<hi) {
            sum = numbers[lo]+numbers[hi];
            if(sum == target) return new int[] {lo+1, hi+1};
            else if(sum < target) lo++;
            else hi--;
        }
        return new int[] {};
    }
}

최악의 경우 O(N)의 시간 복잡도로 문제를 해결할 수 있다.