투 포인터

투포인터 알고리즘

• 투포인터 알고리즘 혹은 슬라이딩 윈도우 라고 부름

  1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작해가며 원하는 것을 얻어내는 알고리즘

• 대표적인 문제로 1차원 배열에서 원소의 합이 M이 되도록하는 경우의 수 구하기

방법

1. 포인터를 2개 준비, 시작과 끝을 알 수 있도록 start, end로 명시
2. 처음은 start = end = 0 에서 시작, 항상 start <= end를 만족해야 함
3. 2개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할
4. 만약 현재 부분합이 M 이상이거나, 이미 end = N(배열의 끝)이면 start++
5. 그렇지 않다면 end++
6. 현재 부분합이 M과 같으면 start++, cnt++

시간 복잡도

• O(N)