양의 정수 배열 A가 있다고 가정하고 해당 하위 배열의 다른 정수 수가 정확히 K인 경우 A의 좋은 하위 배열(연속)을 호출할 수 있습니다. 따라서 배열이 [1,2,3,1 ,2]에는 1, 2, 3의 3가지 정수가 있습니다. 우리는 A의 좋은 부분배열의 수를 찾아야 합니다.
따라서 입력이 [1,2,3,1,4]이고 K =3인 경우 출력은 4가 됩니다. 정확히 4개의 고유한 정수로 3개의 하위 배열을 형성할 수 있기 때문입니다. 이들은 [1,2,3 ], [1,2,3,1], [2,3,1], [3,1,4].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
atMost() 함수를 정의하면 배열 a와 변수 k가 필요합니다.
-
하나의 세트 전류 정의
-
j :=0, ans :=0, n :=a
의 크기 -
하나의 맵 정의
-
initialize i :=0의 경우, i
-
m[a[i]]가 0이면 m[a[i]]를 1만큼 증가시킨 다음 -
-
k <0일 때 −
-
m[a[j]]를 1만큼 감소시키고 m[a[i]]가 0이면 -
-
(k를 1씩 증가)
-
-
(j를 1씩 증가)
-
-
-
x :=((i - j) + 1)
-
as :=ans + x
-
-
반환
-
주요 방법에서 다음을 수행하십시오 -
-
반환 atMost(a, k) - atMost(a, k - 1);
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subarraysWithKDistinct(vector<int>& a, int k) {
return atMost(a, k) - atMost(a, k - 1);
}
int atMost(vector <int>& a, int k){
set <int> current;
int j = 0;
int ans = 0;
int n = a.size();
unordered_map <int, int> m;
for(int i = 0; i < a.size(); i++){
if(!m[a[i]]++) k--;
while(k < 0){
if(!--m[a[j]])
k++;
j++;
}
int x = ((i - j) + 1);
ans += x;
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,1,4};
cout << (ob.subarraysWithKDistinct(v, 3));
} 입력
{1,2,3,1,4}, 3 출력
4