투 포인터와 슬라이딩 윈도우

Two Pointers와 Sliding Window의 차이점?

두 알고리즘은 1차원 배열을 2번 이상 반복적으로 탐색해야 할 경우 시간복잡도가 O(N^2) 걸리는 것을 O(N)으로 줄일 수 있다는 공통점이 있다. 이런 공통점을 가진 알고리즘의 차이점은 투포인터에서는 부분배열의 길이가 가변적이지만 슬라이딩 윈도우는 부분배열의 길이가 고정적이다.

Two Pointers

• 두 포인터가 같은 방향으로 진행하거나
• 두 포인터가 양끝에서 시작하여 진행되거나

부분배열이 연속성이 있어야 한다.
두 포인터를 start, end로 지정을 한다.

1. 부분배열의 합이 target보다 크거나 같고 또는 end가 부분배열의 길이와 같다면 start++
2. 그렇지 않으면 end++
3. 부분배열의 합이 target과 같다면 result+1

Sliding Window

• 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용하다. 중복요소 재사용!

슬라이딩 윈도우는 부분배열의 길이가 고정적이기 때문에 포인터 변수가 2개일 필요가 없다. 부분배열의 길이가 고정적이기 때문에 부분배열의 시작을 알면 끝도 알 수 있기 때문이다.