[리트코드(LeetCode)] 167번 Two Sum 2 - 파이썬/python

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

정렬된 배열을 받아 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하는 문제다. (배열은 0이 아닌 1부터 시작)

예시

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

풀이

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            lo = i + 1
            hi = len(numbers) - 1

            while lo <= hi:
                mid = (lo + hi) // 2

                if numbers[mid] == target - numbers[i]:
                    return [i + 1, mid + 1]
                elif numbers[mid] < target - numbers[i]:
                    lo = mid + 1
                else:
                    hi = mid - 1

 

- 주어진 배열은 정렬되어 있기 때문에 특정 값을 찾기 위해 이진 탐색을 활용한다.

- 각 숫자를 기준으로 배열을 반복하며 두 번째 숫자를 이진 탐색을 사용하여 찾고 타겟과 현재 숫자를 뺀 값이 일치하는지 확인한다.

- 일치하면 두 숫자의 합이 타겟과 같으므로 두 숫자를 인덱스가 1부터 시작하는 형태로 반환한다.