- Two Sum II - Input Array Is Sorted
링크텍스트
인풋으로 들어온 numbers 배열 중 더해서 target 값이 되는 두 요소를 찾는 문제이다.
투포인터를 이용해서 풀었다.
배열의 처음을 가리키는 start 포인터와 배열의 끝을 가리키는 end 포인터를 선언하고,
두 포인터가 가리키는 수의 합이 target 값과 같을 때까지 반복문을 돈다.
두 포인터가 가리키는 수의 합이 target 값보다 클 경우 end 포인터를 하나 감소하고,
두 포인터가 가리키는 수의 합이 target 값보다 작을 경우 start 포인터를 하나 증가한다.
최종적으로 그 두 수를 가리키는 인덱스를 반환한다. (이 문제에서는 인덱스가 1부터 시작해서 1을 더해줌.)
class Solution(object):
def twoSum(self, numbers, target):
start = 0
end = len(numbers)-1
while True:
if numbers[start] + numbers[end] == target:
break
elif numbers[start] + numbers[end] > target:
end -= 1
start = 0
elif numbers[start] + numbers[end] < target:
start += 1
return (start+1, end+1)