2 minute read

167. Two Sum II - Input Array Is Sorted

문제 링크

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

문제 설명

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

제한 사항

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

입출력 예 #1

  1. Input : numbers = [2,7,11,15], target = 9
  2. Output : [1,2]
  3. Explanation : The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

입출력 예 #2

  1. Input : numbers = [2,3,4], target = 6
  2. Output : [1,3]
  3. Explanation : The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

입출력 예 #3

  1. Input : numbers = [-1,0], target = -1
  2. Output : [1,2]
  3. Explanation : The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

문제 풀이

  1. 투 포인터 방식 풀이
  2. 이진 검색 풀이
  3. bisect 모듈 + 슬라이싱 기법 풀이
  4. bisect 모듈 + 슬라이싱 제거
class Solution:
    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  # 인덱스가 0이 아닌 1부터 시작하기에 

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for k, v in enumerate(numbers):
            left, right = k + 1, len(numbers) - 1
            expected = target - v
            # 이진 검색으로 나머지 값 판별
            while left <= right:
                mid = left + (right - left) // 2
                if numbers[mid] < expected:
                    left = mid + 1
                elif numbers[mid] > expected:
                    right = mid - 1
                else : 
                    return k + 1, mid + 1

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

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

Comments

You May Also Enjoy