투 포인터(Two Pointers)알고리즘

투 포인터(Two Pointers)알고리즘

1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 원하는 값을 찾을 때 까지 탐색하는 알고리즘

배열의 양끝에서 시작하는 두 포인터를 점진적으로 이동시켜 문제를 해결하는 방식

 

시간복잡도는 O(n)

 

과정 

1. 두개의 포인터를 사용해 하나는 배열의 왼쪽 끝(Start)에서 시작하고, 다른 하나는 배열의 오른쪽 끝(End)에서 시작한다.

2. 두 포인터를 상황에 맞게 점진적으로 이동하여 문제를 해결

3. 배열을 여러 번 반복하지 않고, 한 번의 반복으로 문제를 해결한다.

 

투 포인터 알고리즘은 주로 정렬된 배열인

두 수의 합, 부분합, 가장 긴 부분 문자열 찾기에 사용된다. 

 

코드 구현 예제

주어진 정렬된 배열에서, 두 수를 더했을 때 특정한 값이 되는 인덱스 쌍 찾기