Two Pointer Algorithm

투 포인터 알고리즘

• 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 값 찾을 때까지 탐색하는 알고리즘
• 리스트에 순차적으로 접근해야 할 때 두 포인트의 위치를 기록하며 처리
• 처음은 start = end = 0
• 두 포인터는 항상 start <= end를 만족해야만 한다. 

시간 복잡도

• 루프마다 두 포인터 중 하나는 1씩 증가하므로 start와 end는 최대 N까지 증가 가능
• 증가하는 과정은 최대 N번 반복
• O(N^2)가 걸리는 문제를 O(N)에 해결 가능하다.