규칙을 만족하는 윈도 개수 세기

때로는 가장 긴 부분 배열을 찾는 것이 아니라 규칙을 만족하는 부분 배열의 개수를 세어야 합니다. 간단한 요령을 사용하면 이를 쉬운 슬라이딩 윈도 문제로 바꿀 수 있습니다. 🔢

어떤 값이 정확히 K개인 부분 배열을 직접 세는 일은 까다롭습니다. 경계가 계속 바뀌기 때문에 하나의 깔끔한 윈도를 유지하기 어렵습니다.

최대 K개인 부분 배열을 세는 것은 하나의 윈도로 훨씬 쉽습니다. 오른쪽으로 확장할 때 유효한 왼쪽 경계마다 하나의 부분 배열을 셀 수 있습니다.

정확히 K개인 경우는 atMost(K)에서 atMost(K - 1)을 뺀 것과 같습니다. 쉬운 두 개의 개수를 결합하면 실제로 원하는 어려운 개수를 얻을 수 있습니다.

최대 k개인 부분 배열의 개수를 세는 함수를 하나 작성하십시오. 이 함수는 윈도를 이동하다가 개수가 k를 초과할 때마다 줄입니다.

오른쪽으로 확장하고 윈도를 갱신합니다. 윈도에 k보다 더 많은 항목이 있는 동안 왼쪽을 앞으로 이동하여 범위 안으로 되돌립니다.

윈도를 수정한 뒤에는 왼쪽부터 시작하여 오른쪽에서 끝나는 모든 부분 배열이 유효합니다. 오른쪽에서 왼쪽을 뺀 값에 1을 더한 값을 더하십시오.

오른쪽을 고정하면 유효한 시작점은 왼쪽, 왼쪽+1부터 오른쪽까지입니다. 따라서 정확히 right - left + 1개의 부분 배열이 있으며, 모두 최대 k개라는 조건을 만족합니다.

보조 함수를 두 번 실행한 뒤 빼십시오. 각 호출은 O(n)이므로 전체 정확히 K개 개수도 여전히 선형 시간에 구할 수 있습니다.

k가 0이면 atMost(k - 1)에서 음수 1을 사용하게 됩니다. 이 경우를 처리하여 보조 함수가 여전히 의미 있는 0개의 결과를 반환하도록 하십시오.

이 최대 개수끼리 뺄셈하는 방식은 서로 다른 값이 정확히 K개인 부분 배열, 홀수가 K개인 부분 배열 또는 윈도마다 단조롭게 변하는 속성의 개수를 세는 데 사용할 수 있습니다.

서로 다른 요소가 정확히 K개인 부분 배열의 개수를 세려고 합니다.

정확히 K개인 경우를 세는 것은 atMost(K)에서 atMost(K - 1)을 뺀 것일 뿐입니다. 각 보조 함수는 O(n)에 윈도를 이동하므로 전체 개수도 선형 시간에 구할 수 있습니다. ✅