Two Sum II - Input Array Is Sorted

Two Sum II - Input Array Is Sorted

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

문제

오름차순으로 더해진 numbers 배열에서 합이 target이 되는 두개의 수를 골라 return

풀이

• 배열의 최대 길이가 30000이므로 O(n^2) 풀이는 시간초과가 발생할 것이다.
• 문제에서 정렬된 배열에서 두개의 수를 고르라는 부분은 two pointer 문제라는 힌트다.
• 앞 뒤로 탐색할 left, right 포인터를 선언한다.
• 하나의 솔루션만 존재한다고 써있으므로 현재 더한 값이 target과 같다면 left + 1, right + 1을 리턴한다.
• target보다 작을 때 작은 수를 가리키는 left의 위치를 +1 시켜준다.
• target보다 클 때, 큰 수를 가리키는 right의 위치를 -1 시켜주어 값을 감소시킨다.

수도 코드

left = 0, right = numbers.length - 1
while left < right:
	total = numbers[left] + numbers[right]
    if total과 target이 같다면
    	return [left + 1, right + 1]
   	if total이 target보다 작다면
    	left++
 	else # total > target
    	right++

Solution(Runtime: 2ms)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int left = 0, right = numbers.length - 1; left < right; ) {
            if (numbers[left] + numbers[right] == target) {
                return new int[] {left + 1, right + 1};
            }
            if (numbers[left] + numbers[right] < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] {};
    }
}

투포인터 풀이말고도 HashMap을 이용한 풀이가 있었다. numbers 배열을 순회하면서 map에 numbers[i] = i + 1 을 저장하고 target - numbers[i]가 map에 존재하는 경우, {map[target - numbers[i], i + 1}을 리턴하는 방식이다.

map = dict()
for i in range(n):
	if target - numbers[i] in map:
    	return [map[target - numbers[i], i + 1]
    map[numbers[i]] = i + 1

target - numbers[i]를 찾는 이유는 target을 만드려면 numbers[i]이외에 다른 하나는 target - numbers[i]이다. 하나의 수가 map에 존재하면 target이 만들어지는 점을 이용한 것 같다.