[Leet Code] Two Pointers (투포인터): 167. Two Sum 2 - Input Array Is Sorted - Medium

* Two Pointers 알고리즘 설명

 

문제 / 코드

 

 개인적으로 medium 중 제일 쉬웠던 문제. Two pointers에서 항상 중앙값을 가지고 풀던 것을 끝 값을 활용하는 것으로 아이디어만 바꾸면 수월하게 풀 수 있는 문제이다.

 

Description

 Find two numbers such that they add up to a specific target number and return a list of those integers' index in the input array.

 

Condition

- The input array is 1-indexed

- The array is already sorted in non-decreasing order

- There is only one solution

- You may not use same number twice

- Your solution must use only constant extra space (SC=o(n))

- Returned list should be sorted in increasing order

 

How to solve

 We need to find integer a, b which makes a+b=target.

 

 So,

1. let a points the smallest number and let b points the biggest number in the array.
2. If a+b is target, we just can return [index of a , index of b]. Since the input array is already sorted in decreasing order, the index of a is always smaller than the index of b because a points a smaller number than b.
3. If a+b > target, it means we need to make a+b smaller. Since a started from the smallest number in the array, we can't decrese it. So move b to right left number to decrease the number b points.
4. If a+b < target, it means we need to make a+b bigger. Since b started from the biggest number in the array, we can't increase it. So move a to right right number to increase the number a points.

 Until the condition 2 is satisfied or a=b  - which means a pointed all numbers at the left side and b pointed all numbers at the right side of the array and now they're pointing same number = at the middle of the array -, we can repeat 3~4.

 

Pseudo Code

start, end = 0, len(numbers)-1

whlie start != end:
	if array[start] + array[end] == target:
    	return [start+1, end+1] # The array is 1 indexed, so we need to +1
    elif array[start] + array[end] > target:
    	end-=1
    else:
    	start+=1