LeetCode 풀기 - 167. Two Sum II - Input Array Is Sorted

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)

 

배열을 순차적으로 탐색하면서 target에서 특정 값을 뺐을 때 원하는 값이 있는지 hash를 체크해서 풀 수 있다.

a + b = target  ---> a = target - b

 

시간 복잡도 : O(n)

공간 복잡도 : O(n)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        d = {}
        for i, n in enumerate(numbers):
            diff = target - n
            if diff in d:
                return [d[diff]+1, i+1]
            else:
                d[n] = i

솔루션2)

투 포인터를 이용해서 문제를 푸는 방법도 있다.

 

시간 복잡도 : O(n)

공간 복잡도 : O(1)

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