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

167. Two Sum II - Input Array Is Sorted

방법_#1 투포인터

time : O(N)
space: O(1)

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(numbers)
        low = 0
        high = n - 1

        while (low < high):
            value = numbers[low] + numbers[high]

            if (value == target):
                return [low + 1, high + 1]
            elif (value < target):
                low += 1
            else:
                high -= 1

방법_#2 이분탐색

time O(NlogN)
space O(1)

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

        i = 0
        n = len(numbers)

        for i in range(n):
            f = numbers[i]
            low = i + 1
            high = n - 1

            while (low <= high):
                t = target - f
                mid = low + (high - low) // 2

                if (numbers[mid] == t):
                    return [i+1, mid + 1]
                elif (numbers[mid] < t):
                    low = mid + 1
                else:
                    high = mid - 1