투포인터(Two Pointers)

두 가지 포인터를 사용하여 문자열이나 배열에서 원하는 값을 찾거나 반복문을 써야 할 때 쓰기 좋은 방식.

---

투포인터 알고리즘

ex) 10 5
1 2 3 4 2 5 3 1 1 2에서 합이 5인 개수 세기

두 개의 포인터 (start와 end)를 0으로 초기화

---

빨간색과 파란색을 시작지점에 두고 파란색을 점차 늘린다.

---

S(합)가 5를 넘었기 때문에 빨간색을 증가 시킨다

---

S(합)가 5이기 때문에 카운트 해주고 빨간색을 증가시킨다.-

---

합이 5가 넘으면 카운트 해주고 계속해서 반복.

---

계속 증가 시키다 파란색이 10(최대치)에 이르면 종료한다.

---

시간 복잡도는 O(n)이다.

---

슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우(Sliding Window)는 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만 부분 배열의 크기(길이)가 고정적이다.

---

투 포인터와 차이점

투 포인터

1. 부분 배열의 길이가 가변적이기 때문에 부분 배열의 구간을 정할 2개의 포인터 변수가 필요

슬라이딩 윈도우

1. 부분 배열의 길이를 고정적으로 잡기에 포인터 변수가 2개일 필요가 없음

참조문서
https://bbangson.tistory.com/72

---