Two Pointer

투 포인터 알고리즘은 두 개의 포인터를 사용해 원하는 연속합을 찾아낸다.

하나의 포인터는 시작점, 다른 하나의 포인터는 끝점을 나타낸다. 시작점부터 끝점까지의 합이 원하는 연속합 S에 해당한다면 카운트한다. 투 포인터 알고리즘은 다음 과정을 거친다.

1. 시작점과 끝점을 배열의 맨앞의 인덱스로 나타낸다.

2. 연속합을 S와 비교한다.

   1. 연속합이 S와 같다면, 카운트한다.

   2. 연속합이 S보다 작다면, 끝점을 증가시킨다.

   3. 연속합이 S보다 크다면, 시작점을 증가시킨다.

3. 시작점이 범위 끝에 도달할 때 까지 2번 과정을 반복한다.

투 포인터 알고리즘을 사용하지 않고 각 인덱스 별로 반복해서 탐색하는 경우 $O(N^2)$ 시간복잡도를 가질 수 있다.

하지만 투 포인터 알고리즘을 사용하면, 각 포인터는 총 N번 증가되므로 $O(N)$ 시간복잡도로 수행할 수 있다.