리트코드 167번 Two Sum2 - Input Array is Sorted (python)

Problem

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

Solution

내 풀이

from typing import List

class Solution:
    def search(self, numbers: List[int], target: int) -> int:
        left, right = 0, len(numbers) - 1
        while left <= right:
            mid = (left + right) // 2
            if numbers[mid] < target:
                left = mid + 1
            elif numbers[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for idx, num in enumerate(numbers, start=1):
            idx2 = self.search(numbers[idx:], target-num)
            if idx2 != -1:
                return [idx, idx + idx2 + 1]

원소를 하나씩 뽑아서 그 뒤의 원소들을 탐색하며 원하는 값을 찾았다. 이진 탐색을 이용하여 $O(nlogn)$으로 해결하였다.

다른 풀이

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for idx, num in enumerate(numbers, start=1):
            expect = target - num
            expect_idx = bisect.bisect_left(numbers, expect, lo=idx)

            if expect_idx < len(numbers) and numbers[expect_idx] == expect:
                return [idx, expect_idx+1]

bisect 모듈을 이용하여 이진검색을 하면 약 9배 빠른 성능을 보인다.

Reference

파이썬 알고리즘 인터뷰 68번