슬라이딩 윈도우 / 투 포인터 (JAVA)

부분 배열을 활용하여 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우의 O(N^2) 이상의 시간 복잡도를 O(N)으로 줄일 수 있다. 윈도우가 이동하면서 윈도우 내의 데이터를 이용하여 문제를 해결하는 알고리즘.

슬라이딩 윈도우 

: 부분 배열의 길이가 고정적

배열이 고정적이기 때문에 포인터가 하나만 있어도 된다. 기존 구간에서 빠지게 되는 가장 왼쪽칸의 값을 삭제하고 새 구간에 포함되는 값을 추가해주면 된다.

우선순위 큐를 활용하기도 한다.

 

적용 문제 : https://tech-heng.tistory.com/93

 

투포인터

: 부분 배열의 길이가 가변적

모든 배열의 값들을 필연적으로 탐색하여 특정 조건을 일치시키는 개수 혹은 최소,최대 값 찾는 문제에서 연속되고 가변적인 부분 배열을 활용

1) 2개의 포인터 변수 시작점이 배열의 시작점인 경우

2) 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점 (arr.length-1)에 위치한 경우

 

정수로 이루어진 배열에서 연속된 부분 배열의 합이 특정 값(Target)을 이루는 부분 배열의 개수를 구하는 문제가 있다고 가정했을 때, 두 포인터 변수의 이동 조건은 다음과 같습니다. 

(1) 부분 배열의 합이 Target 값보다 크거나 같으면  Left = Left + 1 (부분 배열의 길이를 줄여 합을 빼준다. )

if(sum >= Target) Left++;

(2) 부분 배열의 합이 Target 값보다 작으면 Right = Right + 1 (부분 배열의 길이를 늘려 합을 더한다.)

if(sum < Target) Right++;

(3) 부분 배열의 합이 Target 값과 같다면 결과 값을 +1

if( sum == Target) count++;

 

적용 문제 :