728x90
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.
non-decreasing order : 감소하지 않는. 즉, 증가하거나 / 같은 숫자들이 나오는
타겟을 만족시키는 솔루션은 하나이므로 바로 리턴하면 된다.
Your solution must use only constant extra space.
-> 공간복잡도를 신경쓰라는 의미! 입력 크기에 따라 달라지지 않는 고정된 크기의 메모리 공간을 사용해야 한다.
풀이1: 브루트포스 (시간 초과)
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers)):
for j in range(i+1, len(numbers)):
if numbers[i] + numbers[j] == target:
return [i+1, j+1]
return []구현 자체는 브루트포스를 통해 쉽게 할 수 있다.
이 풀이는 공간복잡도는 O(1)이지만, 시간복잡도는 O(n^2)이다.
그리고 리트코드에서는 시간초과가 나서 통과하지 못했다.
풀이2: Two Pointers
Two Pointers 방식으로 풀면 더 효율적인 풀이가 가능하다.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while l < r:
curSum = numbers[l] + numbers[r]
if curSum > target:
r -= 1
elif curSum < target:
l += 1
else:
return [l+1, r+1]
return []배열 전체를 한번 탐색하므로 시간 복잡도는 O(n)이며,
별도의 추가 공간 없이 배열 내에서 포인터만 움직이므로 공간 복잡도는 O(1)이다.
문제 조건에서의 Two Pointers 접근 힌트
문제에서 Two Pointers로 접근하면 효율적이라는 것을 알 수 있는 여러 조건이 있다.
1. non-decreasing order
정렬된 배열이 주어진다는 것이다. Two Pointer 접근은 배열이 정렬되어 있을 때 두 값을 연산하거나 비교할 때 효과적이다.
2. exactly one solution
이 조건이 없으면 모든 조건을 찾아야 해서 이중 반복문을 써야할 수도 있지만,
이 문제에서는 반드시 하나의 solution만 존재하기 때문에 투포인터가 한번만 움직여도 답을 찾을 수 있다.
728x90