✍️ 코테 준비/Binary Search

[LeetCode] 167. Two Sum II - Input Array Is Sorted

고도고도 2022. 6. 9. 19:36

입력 예시

풀이 언어

Python

풀이 방법

정렬된 배열에서 target을 만족하는 두 원소의 index를 반환하는 문제였다. 오름차순을 정렬된 배열이었기에 BST 문제라고 생각했다. 어렵지 않게 해결했다.

코드

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        start = 0
        end = len(numbers) - 1
        
        while start < end:
            mid = numbers[start] + numbers[end]
            if mid > target:
                end -= 1
            elif mid < target:
                start += 1
            else:
                return [start + 1, end + 1]

결과