투포인터

투포인터란?

배열 [1, 2, 3, 2, 5] 가 주어졌을 때 합이 5인 부분 연속 수열 갯수를 알고 싶다 라고 가정해보자

브루트포스 사용하면 O(N^2)를 사용해서 찾을 수 있다.
하지만 투 포인터를 사용하면 O(N)으로 찾을 수 있다.

[초기단계] 시작점과 끝 점이 첫 번째 원소 인덱스를 가리키도록 한다.

[Step 1] 현재 부분합은 1이므로 end를 1 증가시킨다.

[Step 2] 현재 부분합은 3이므로 end를 1 증가시킨다.

[Step 3] 현재 부분합은 5이므로 count를 1 증가시킨다. 또한 start를 1증가시킨다.

[Step 4] 현재 부분합은 3이므로 end를 1증가시킨다.

[Step 5] 현재 부분합은 5이므로 count를 1 증가시킨다. 또한 start를 1증가시킨다.

[Step 6] 현재 부분합은 2이므로 end를 1증가시킨다.

[Step 7] 현재 부분합은 7이므로 start를 1증가시킨다.

[Step 8] 현재 부분합은 5이므로 count를 1 증가시킨다. 또한 start를 1증가시킨다.

이렇게 하여 부분합이 5인 개수를 구할 수 있다.

뿐만 아니라
정렬된 배열에서 특정 값과 가장 가까운 값도 찾을 수 있다.