예를 들어, 배열을 입력으로 받고 두 개 이하의 다른 숫자를 포함하는 배열의 최대 슬라이스를 반환하는 함수를 작성해야 한다고 가정해 보겠습니다. 이 문제를 자세히 살펴보면 안정적인 하위 배열을 확인하고 원본 배열을 반복하는 작업이 포함됩니다.
따라서 슬라이딩 윈도우 알고리즘이 이에 매우 적합합니다. 슬라이딩 윈도우 알고리즘을 통해 이 문제를 해결하는 코드는 -
예시
const arr = [1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8, 1, 1 ,1 ,1, 8, 1,
1, 8, 8];
const map = {
length: 0
};
let required = [];
for(start = 0, end = 0; end <= arr.length; ){
if(map.length > 2){
if(map[arr[start]] === 1){
delete map[arr[start]];
map.length --;
}else{
map[arr[start]]--;
};
start++;
}else{
if(end - start > required.length){
required = arr.slice(start, end);
};
if(map[arr[end]]){
map[arr[end]]++;
}else{
map[arr[end]] = 1;
map.length++;
}
end++;
}
}
console.log(required); 배열의 임의 지점에서 고유한 문자 수를 저장하기 위한 맵을 유지하고 각 반복에서 가장 긴 하위 배열의 길이를 계속 비교했습니다. 고유한 문자 수가 2를 초과하면 배열을 오른쪽으로 슬라이드하여 다음 안정적인 배열을 찾습니다.
출력
콘솔의 출력은 다음과 같습니다. -
[ 1, 8, 1, 1, 1, 1, 8, 1, 1, 8, 8 ]