167 Two Sum II - Input array is sorted

• 167 Two Sum II - Input array is sorted
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 생각
      • 1 코드
      • 1 결과: 성공
    • 2nd
      • 2 생각
      • 2 코드
      • 2 결과: 성공

167 Two Sum II - Input array is sorted

문제

Given an array of integers numbers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.
You may assume that each input would have exactly one solution and you may not use the same element twice.

조건

• $2 \le numbers.length \le 3 * 10^{4}$
• $-1000 \le numbers[i] \le 1000$
• numbers is sorted in increasing order
• $-1000 \le target \le 1000$
• Only one valid answer exists

예제

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

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Input: numbers = [-1,0], target = -1
Output: [1,2]

해결

1st

1 생각

• 정렬된 상태의 숫자 배열을 받고, 합해서 타겟이 되는 조합을 찾아낸다.
• 이진 탐색의 장에 있으니, 탐색을 활용해서 풀어보자

1 코드

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    def bi_search(num):
        numbers_len = len(numbers)
        result = None
        left = 0
        right = numbers_len - 1

        while left <= right and left < numbers_len and right < numbers_len:
            mid = left + (right - left) // 2
            if numbers[mid] > num:
                right = mid - 1
            elif numbers[mid] < num:
                left = mid + 1
            else:
                result = mid
                break

        return result
    ans = []
    idx = 0
    while idx < len(numbers):
        first = numbers[idx]
        result = bi_search(target - first)
        if result is not None and result != idx: # 같은 요소를 쓰지 말아야 한다
            return sorted([idx + 1, result + 1]) # 오름차순이어야 한다
        idx += 1
    
    return []

1 결과: 성공

Runtime: 96 ms, faster than 11.53% of Python3 online submissions for Two Sum II - Input array is sorted.
Memory Usage: 14.5 MB, less than 96.14% of Python3 online submissions for Two Sum II - Input array is sorted.

하지만 기존에 golang으로 풀었을 때는 4ms여서, 속도 차가 심하다

func twoSum(numbers []int, target int) []int {
  ans := make([]int, 0, 2)
  numbersLen := len(numbers)
  /*
  오름차순으로 정렬되어 있으므로, 아래에서 위로 움직는 i와 위에서 아래로 움직이는 j로 좁힐 수 있다.
   */
  i, j := 0, numbersLen - 1
  loop:  /* label */
  for i < j {
    tmp := numbers[i] + numbers[j]
    if tmp == target {
      ans = append(ans, i + 1, j + 1)
      break loop
    } else if tmp > target {
      /* 타겟보다 크면 큰 값을 줄여나간다 */
      j--
    } else {
      /* 타겟보다 작으면 작은 값을 늘려나간다 */
      i++
    }
  }

  return ans
}

2nd

2 생각

• golang 풀이처럼 좌/우 포인터를 움직이면서 값을 확인해 보자

2 코드

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    numbers_len = len(numbers)
    left = 0
    right = numbers_len - 1

    while left < right:
        if numbers[left] + numbers[right] < target:
            left += 1
        elif numbers[left] + numbers[right] > target:
            right -= 1
        else:
            return [left + 1, right + 1]

2 결과: 성공

Runtime: 56 ms, faster than 94.22% of Python3 online submissions for Two Sum II - Input array is sorted.
Memory Usage: 14.7 MB, less than 59.43% of Python3 online submissions for Two Sum II - Input array is sorted.

이진 탐색 방식보다는 빠르지만, 그래도 컴파일 언어보다는 느리다