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

문제링크

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

Two Sum II - Input Array Is Sorted - LeetCode

 

코드

풀이1

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

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

 

POINT

풀이1

two pointers를 적용하였다. numbers가 오름차순으로 배치되어있기 때문에 left, right two pointers를 사용하여 그 합을 구하고 target와 비교한다. target보다 더 크면 (left+1, right)로 탐색 범위를 변경고, 더 작으면 (left, right-1)로 탐색 범위를 변경한다.

Time Complexity : O(n)

 

풀이2

numbers 배열 순서대로 기준값이 되고, 이 기준값에 어떤 값을 추가로 더하여 그 합이 target이 될 지 찾는다. 이때 추가로 더할 값을 찾기 위해 이진탐색을 적용하였다. numbers가 오름차순으로 배치되어있기 때문에 left, right two pointers를 사용하여 그 가운데 인덱스 값(mid)과 현재 기준값과의 합을 구하고 target와 비교한다. target보다 더 크면 (left, mid-1)로 탐색 범위를 줄이고, 더 작으면 (mid+1, right)로 탐색 범위를 변경한다.

Time Complexity : O(nlogn)