투 포인터 알고리즘
- 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 값 찾을 때까지 탐색하는 알고리즘
- 리스트에 순차적으로 접근해야 할 때 두 포인트의 위치를 기록하며 처리
- 처음은 start = end = 0
- 두 포인터는 항상 start <= end를 만족해야만 한다.
시간 복잡도
- 루프마다 두 포인터 중 하나는 1씩 증가하므로 start와 end는 최대 N까지 증가 가능
- 증가하는 과정은 최대 N번 반복
- O(N^2)가 걸리는 문제를 O(N)에 해결 가능하다.
