[Leetcode]#2606-Two Sums2

Problem

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.

[문제 해석]

오름 차순으로 정렬된 list가 있다. list 내의 2개의 숫자들을 더했을 때 target 숫자가 될 경우 [index1+1, index2+1] 해당 숫자의 인덱스에 +1을 하여 리스트 형태로 출력하시오.

Example

Example 1:

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. We return [1, 2].

Example 2:

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

Example 3:

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

Constraints:

• 2 <= numbers.length <= 3 * 104
• 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.

Solution

🚨 이 문제의 핵심

• left 와 right를 어떤 값으로 초기화 할 것인지
• 반복을 언제 멈출지
• 언제 pointer를 옮길 것인지

이 문제의 핵심

• left 와 right를 어떤 값으로 초기화 할 것인지

⇒ left = 0, right = len(numbers) - 1

• 반복을 언제 멈출지

⇒ left ≤ right : index의 값이 옆으로 한 칸씩 옮기되, 정반대 방향에서 오는 것과 만나면 중지!

• 언제 pointer를 옮길 것인지

⇒ 오름차순으로 나열된 배열이기 때문에

• 가장 작은 값과 가장 큰 값의 합이 target보다 작으면 ⇒ 가장 작은 값을 이동시켜 큰 값을 적용
• 가장 작은 값과 가장 큰 값의 합이 target보다 크면 ⇒ 가장 큰 값을 이동시켜 작은 값을 적용
• 가장 작은 값과 가장 큰 값의 합이 target과 같다면 ⇒ 정답으로 return

⭐ 문제를 푸는데 있어서 O(n)을 크게 신경쓰면서 풀지 않는 것을 추천한다!

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left <= right:
            a = numbers[left]
            b = numbers[right]
            if a + b == target:
                return [left+1, right + 1]
            elif a + b < target:
                left += 1
            else:
                right -= 1

++ 소감

• two pointer 문제라는 사실은 자명하나, 모든 문제가 이런 방식으로 풀리는지 의문임
• 오름차순 이라는 조건이 굉장히 중요한 요소임
• 생각보다 수학적으로 풀려서 껌연쩍다 ..