LeetCode 167. Two Sum II - Input Array Is Sorted

파이썬 알고리즘 인터뷰 68번(리트코드 167번) Two Sum II - Input Array Is Sorted
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

나의 풀이1(이진 검색)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            remainder = target - numbers[i]
            left, right = i + 1, len(numbers) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if numbers[mid] > remainder:
                    right = mid - 1
                elif numbers[mid] < remainder:
                    left = mid + 1
                else:
                    return [i + 1, mid + 1]

나의 풀이2(Two Pointers, 투 포인터)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left <= right:
            curr = numbers[left] + numbers[right]
            if curr > target:
                right -= 1
            elif curr < target:
                left += 1
            else:
                return [left + 1, right + 1]
        
        # 왜 처음에 투 포인터를 생각하지 못하고 이진 검색을 생각했을까?

다른 풀이(이진 검색 모듈 이용)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for k, v in enumerate(numbers):
            expected = target - v
            # nums = numbers[k + 1:] - 슬라이싱하면 느려진다. 대신 bisect 의 파라미터로 k + 1 넣기
            i = bisect.bisect_left(numbers, expected, k + 1)
            if i < len(numbers) and numbers[i] == expected:
                return k + 1, i + 1