সমস্যা বিবরণ
একটি অ্যারে A দেওয়া থাকলে, যেসব সংলগ্ন সাবঅ্যারেতে ঠিক Kটি ভিন্ন ইন্টিজার থাকে তাদের সংখ্যা বের করতে হবে।
উদাহরণ
A = [1,2,3,1,4], K = 3 → আউটপুট = 4 (সাবঅ্যারে: [1,2,3], [1,2,3,1], [2,3,1], [3,1,4])
সমাধান পদ্ধতি
- স্লাইডিং উইন্ডো + atMost(K) - atMost(K-1) ফর্মুলা ব্যবহার করা হয়।
- atMost(k) ফাংশন দিয়ে কতগুনো সাবঅ্যারেতে hoogst kটি ডISTINCT ইন্টিজার আছে তা বের করা হয়।
- ফ্রিকোয়েন্সি ম্যাপ দিয়ে উইন্ডো মেইনটেইন করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
int atMost(vector<int>& a, int k) {
int j = 0, ans = 0;
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++;
}
ans += (i - j + 1);
}
return ans;
}
public:
int subarraysWithKDistinct(vector<int>& a, int k) {
return atMost(a, k) - atMost(a, k - 1);
}
};
int main() {
Solution ob;
vector<int> v = {1,2,3,1,4};
cout << ob.subarraysWithKDistinct(v, 3);
return 0;
}ইনপুট ও আউটপুট
ইনপুট: {1,2,3,1,4}, 3
আউটপুট: 4
