[리트코드] 167. Two Sum II - Input Array Is Sorted

문제

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150 

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 * 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 투포인터[통과] ⭕ -> 요구사항 충족 ⭕

Intuition

배열이 오름차순 정렬되어있다는 점을 이용하여 배열 맨앞과 맨끝에 투포인토를 두고 가운데로 움직이며 문제를 해결한다.

Algorithm

투포인터 위치의 두 숫자의 합이 만약 target보다 크다면 합친 숫자를 줄여야하기 때문에 오른쪽 포인터의 위치를 한칸 왼쪽을 옮겨준다.  반대로 두 수의 합이 target  보다 작다면 왼쪽 포인터의 위치를 오른쪽으로 한칸 옮겨준다. 이러한 방식으로 두 포인터의 위치를 찾는다.

 

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    p1, p2 = 0, len(numbers) - 1

    while p1 < p2:
        s = numbers[p1] + numbers[p2]

        if s > target:
            p2 -= 1

        elif s < target:
            p1 += 1

        elif s == target:
            break

    return [p1 + 1, p2 + 1]

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • 두개의 포인터로 배열요소를 한번씩 탐색 O(M)
  • 그러므로 전체시작복잡도 : O(N)

• 공간복잡도 : O(1)
  
  • 추가 배열을 사용하지 않음

---

기타풀이 및 회고

문제 조건에서 오름차순 정렬이 되어있었기에 가능한 풀이였다. 배열의 길이가 3 * 10**4 이기 때문에 완전탐색을 통한 문제풀이는 O(N**2) 이므로 안될 것이라고 생각하였고, 투 포인터 아이디어를 생각해냈다.

 

이러한 문제처럼 두개의 포인터를 조정해나가며 배열요소를 한번씩만 탐색하여 시간복잡도를 효과적으로 사용하는것이 풀이의 포인트이다.