[리트코드] 167. 두 수의 합 2 (Python)

LeetCode - The World's Leading Online Programming Learning Platform

문제

정렬된 리스트에서 두 수의 합이 target값이 되는 인덱스 반환하기

과정

• 이진탐색을 이용하여 풀어준다.

 

입력

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

출력

[1,2]

 

풀이

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

 

한 줄 씩 해석해보기

start, end = 0, len(numbers)-1

• 0과 마지막 인덱스 까지 투포인터 생성

while start <= end:
    if numbers[start] + numbers[end] < target:
        start += 1
    elif numbers[start] + numbers[end] > target:
        end -= 1
    else:
        return [start+1, end+1]

• start와 end가 같아지기 전까지 반복한다.
• 만약 start인덱스와 end 인덱스의 값의 합이 target보다 작다면 start+=1
• target보다 크다면 end-=1
• 그게 아니라면 target과 값이 같은것이므로 +1을 해준 후 출력한다.