[LeetCode] 167. Two Sum II - Input Array Is Sorted - 문제풀이

Description

오름차순으로 정렬된 배열이 주어졌을 때 두 요소의 합이 target과 일치하는 배열의 인덱스를 반환하는 문제입니다.

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Solution 1. 전체 탐색(Brute force)

public int[] twoSum(int[] numbers, int target) {

    //1. brute force
    int len = numbers.length;
    for (int i = 0; i < len-1; i++) {
        for (int j = i+1; j < len; j++) {
            if(numbers[i]+numbers[j] == target){
                return new int[]{i+1,j+1};
            }
        }
    }
    return null;

}

전체 탐색을 하며 모든 경우의 수를 계산하여 target과 일치할 경우 해당 인덱스를 반환압니다.

• 시간 복잡도 : O(n^2)
• 공간 복잡도 : O(1)

Solution 2. Two Pointers

public int[] twoSum(int[] numbers, int target) {

    //2. Two Pointers
    int len = numbers.length;
    int start = 0;
    int end = len-1;

    while(start < end){
        int sum = numbers[start] + numbers[end];
        if(target == sum){
            return new int[]{start+1,end+1};
        }else if(target < sum){ // sum을 줄여야하니 end--
            end--;
        }else{ // target < sum){ //sum을 늘려야하니 start++
            start++;
        }
    }
    return null;
}

정렬된 배열이기 때문에 양끝에 두 개의 포인터를 이용해서 근접한 sum을 찾아나가는 방법입니다. sum이 target보다 클경우 오른쪽 포인터(end)를 왼쪽으로 이동시켜 sum을 줄이고 반대경우는 왼쪽 포인터(start)를 이동시켜 sum을 늘려나가는 것을 반복합니다.

• 시간 복잡도 : O(n)
• 공간 복잡도 : O(1)

Reference

Two Sum II - Input Array Is Sorted - LeetCode