[algorithm]slidingwindow

less than 1 minute read

Sliding Window

참고:link

연속되는 값들에서 특정한 합을 찾는 알고리즘

TwoPointer와 차이점은 TwoPointer는 start <= end 조건을 만족하는 서브배열의
길이가 제한이 없지만 Sliding Window는 제한된 길이에서 수행한다.

[1,2,3,4,5] 배열이 있고 합이 5를 찾는 경우 start = 0; end = 0;size=2;

[배열]

0 1 2 3 4
1 2 3 4 5

[TwoPointer]

0 1 2 3 4
start – – – –
end – – – –

start와 end를 늘려가며 사이의 값들을 합한다.
start = 0, end= 0 이므로 sum = 1;

[TwoPointer]

0 1 2 3 4
start end – – –

찾는값 5보다 작으므로 end를 1 증가
start = 0, end = 1 이므로 sum = 1 + 2 => 3;

[TwoPointer]

0 1 2 3 4
– start end – –

찾는값 5보다 작지만 size가 2이므로 start, end 1씩증가 sum = 2 + 3 => 5;

마지막으로 [TwoPointer]

0 1 2 3 4
– – – – start
– – – – end

이 경우에 값 5를 찾을 수 있다.


  • 시간복잡도는 투 포인터와 같이 O(N)
  • DP와 결합해서 사용할 경우 윈도우 사이즈가 정해져 있어서 모든 경우를 저장하지 않는 경우 공간복잡도 O(W):W는 윈도우 사이즈

Updated: