LeetCode Top Interview 150) Two Sum II - Input Array Is Sorted

Question

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.

Constraints:

• 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.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:

---

---

조건에 맞는 오름차순 정렬된 숫자리스트 numbers 내에서, 두 원소의 합이 target과 같은 원소를 찾아 원소인덱스를 반환합니다.
이 문제에서 정의된 인덱스는 1부터 시작입니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        idx1,idx2 = 0,len(numbers)-1

        while True:
            num = numbers[idx1]+numbers[idx2]
            if  num < target:
                idx1 += 1
            elif num > target:
                idx2 -= 1
            else:
                return [idx1+1,idx2+1]

• idx1,idx2 : 찾아야할 두 인덱스 변수입니다. 양 끝 인덱스로 초기화합니다.
• while문의 조건이 없어 무한 반복이 될 수 있어 보이지만 조건에서 반드시 답이 있다고 했으므로 while문 내의 return에서 항상 탈출이 가능합니다.
  • 두 값의 합이 target보다 작으면 작은 원소의 인덱스를 올립니다. 오름차순 정렬이 되어 있으므로 값을 올리는 방향입니다.
  • 같은 이유로 target보다 값이 작다면 큰 원소의 인덱스인 idx2의 값을 내립니다.
  • target과 같다면 문제의 인덱스가 1이 시작이라는 점을 감안해서 1씩 더한 값을 반환합니다.

---

오름차순 정렬도 되어 있고 반드시 정답이 있는 상황이였기에 세세하게 체크할 부분은 없는 문제였습니다.

표시된 Medium 난이도치곤 쉽다고 느껴졌던 문제였습니다.

• 이 문제도 그렇지만 메모리나 속도가 미세한 차이로 백분율이 차이나기 때문에 시간복잡도와 공간복잡도에서 차이가 크게 나지 않으면 백분율이 낮아도 신경쓰지 않아도 될 듯 하다!