[🤷‍♀️ LeetCode Python] 167. Two Sum 2 - Input array is sorted

✍

167. Two Sum 2 - Input array is sorted

 

---

문제 및 문제설명

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

Two Sum II - Input array is sorted - LeetCode

내가 쓴 답

# 시간초과로 탈락
def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)-1):
            for j in range(i+1, len(numbers)):
                if numbers[i]+numbers[j] == target:
                    return i+1 , j+1 

 

다른 풀이

#투 포인터 

def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers)-1
        
        while not left == right:
            if numbers[left] + numbers[right] < target:
                left += 1
            elif numbers[left]+numbers[right] > target:
                right -= 1
            else:
                return left+1, right+1
            

#이진검색

def twoSum(self, numbers: List[int], target: int) -> List[int]:
        
        for i, v in enumerate(numbers):
            t = target - v
            idx = bisect.bisect_left(numbers[i+1:], t)
            if idx < len(numbers[i+1:]) and numbers[idx + i + 1] == t:
                return sorted([i+1 , i+idx+2])

 

위의 코드의 실행시간을 줄이기 위해 직접 슬라이싱하는 대신 bisect 모듈 활용

def twoSum(self, numbers: List[int], target: int) -> List[int]:
        
        for i, v in enumerate(numbers):
            t = target - v
            idx = bisect.bisect_left(numbers, t, i+1)
            if idx < len(numbers) and numbers[idx] == t:
                return sorted([i+1 , idx+1])

* bisect.bisect_left(리스트, 해당값, 왼쪽 시작점)

 

출처: 박상길, 파이썬 알고리즘 인터뷰, 책만