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

Two pointer 알고리즘을 활용하여 시간복잡도가 O(n) 이내가 되도록 문제를 풀어야 합니다.

본문

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

Two Sum II - Input Array Is Sorted - LeetCode

---

솔루션

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        index = 0
        pivot_min = 1
        pivot_max = len(numbers)-1
        pivot = len(numbers)//2

        while True:
            if target < numbers[index] + numbers[pivot]:
                pivot_max = pivot -1
            elif target == numbers[index] + numbers[pivot]:
                return [index +1, pivot +1]
            elif target > numbers[index] + numbers[pivot]:
                pivot_min = pivot +1

            # when target is even larger than
            # numbers[index] + numbers[last_index]
            if pivot_max < pivot_min:
                index += 1
                pivot_min = index +1

            # update pivot
            pivot = (pivot_min + pivot_max)//2