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

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

Two Sum II - Input Array Is Sorted - LeetCode

 

Two Sum 문제의 변형으로, 이번엔 input array가 오름차순으로 정렬되어 있다. 

 

 

Solution 1. Brute-force

Time: $O(N^2)$

Space: $O(1)$ 

 

Solution 2. Dictionary (hash table)

Time: $O(N)$

Space: $O(N) (Worst)$

 

Solution 3. Two Pointer

배열이 정렬되어 있는 상황에서 유용하게 사용할 수 있다. 

 

Time: $O(N)$

Space: $O(1)$

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """

        start = 0
        end = len(numbers) - 1

        while True:
            left, right = numbers[start], numbers[end]
            cand = left + right
            if cand > target:
                end -= 1
            elif cand == target:
                return [start + 1, end + 1]
            else:
                start += 1

            if start == end:
                break # No solutions exist