LeetCode - Two Sum II - 입력 배열이 정렬됨

문제 설명

이미 내림차순으로 정렬된 정수 숫자의 1-인덱스 배열이 주어지면 특정 대상 숫자가 되는 두 숫자를 찾습니다. 이 두 숫자를 numbers[index1] 및 numbers[index2]라고 합니다. 여기서 1 <= index1 < index2 <= numbers.length입니다.

두 숫자 index1과 index2의 인덱스를 하나씩 더한 길이 2의 정수 배열 [index1, index2]로 반환합니다.

정확히 하나의 솔루션이 있도록 테스트가 생성됩니다. 동일한 요소를 두 번 사용할 수 없습니다.

솔루션은 일정한 추가 공간만 사용해야 합니다.

문제 진술 출처: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

예 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].

예 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].

예 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].

제약:

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

설명

이진 검색

이 문제는 이전Two Sum 문제와 유사합니다. 숫자를 반환하는 대신 합계가 목표인 인덱스를 반환해야 합니다.

입력 배열이 정렬되어 이진 검색 개념을 쉽고 직접적으로 사용할 수 있습니다. 알고리즘을 직접 확인해 봅시다.

- initialize i = 0, j = numbers.size() - 1
  sum = 0

- loop while i < j
  - sum = numbers[i] + numbers[j]

  - if sum > target
    - decrement: j--
  - else if sum < target
    - increment: i++
  - else
    // when the sum is equal to the target
    - return [i + 1, j + 1]
- while end

- return []

C++, Golang, Javascript에서 알고리즘을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0, j = numbers.size() - 1;
        int sum;

        while(i < j) {
            sum = numbers[i] + numbers[j];

            if(sum > target) {
                j--;
            } else if(sum < target) {
                i++;
            } else {
                return { i + 1, j + 1 };
            }
        }

        return {};
    }
};

골랑 솔루션

func twoSum(numbers []int, target int) []int {
    i, j := 0, len(numbers) - 1
    sum := 0

    for i < j {
        sum = numbers[i] + numbers[j]

        if sum > target {
            j--
        } else if sum < target {
            i++
        } else {
            return []int{ i + 1, j + 1 }
        }
    }

    return []int{}
}

자바스크립트 솔루션

var twoSum = function(numbers, target) {
    let i = 0, j = numbers.length - 1;
    let sum = 0;

    while(i < j) {
        sum = numbers[i] + numbers[j];

        if(sum > target) {
            j--;
        } else if(sum < target) {
            i++;
        } else {
            return [i + 1, j + 1];
        }
    }

    return [];
};

예제 1의 알고리즘을 시험 실행해 보겠습니다.

Input: numbers = [2, 7, 11, 15]
       target = 9

Step 1: set i = 0
            j = numbers.size() - 1
              = 4 - 1
              = 3
            sum = 0

Step 2: loop while i < j
        0 < 3
        true

        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 15
            = 17

        if sum > target
           17 > 9
           true

           j--
           j = j - 1
             = 3 - 1
             = 2

Step 3: loop while i < j
        0 < 2
        true

        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 11
            = 13

        if sum > target
           13 > 9
           true

           j--
           j = j - 1
             = 2 - 1
             = 1

Step 4: loop while i < j
        0 < 1
        true

        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 7
            = 9

        if sum > target
           9 > 9
           false
        else if sum < target
           9 < 9
           false
        else
           return [i + 1, j + 1]
           return [0 + 1, 1 + 1]
           return [1, 2]

We return the answer as [1, 2].