मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी A है। हम 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) होता है:
ठीक K विभिन्न = अधिकतम K विभिन्न - अधिकतम (K-1) विभिन्न
atMost(k) में, दो पॉइंटर्स और एक फ्रीक्वेंसी मैप बनाए रखें
दाएं पॉइंटर का विस्तार करें, विभिन्न गिनती को अपडेट करें
जब विभिन्न > k हो, तो बाएं पॉइंटर को सिकोड़ें
प्रत्येक दाएं स्थिति के लिए, (right - left + 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;
}
};
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
