C++ এ K বিভিন্ন পূর্ণসংখ্যা সহ সাবরে

ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যাগুলির একটি অ্যারে রয়েছে, আমরা A-এর একটি ভাল সাববারে (সংলগ্ন) বলতে পারি, যদি সেই সাব্যারেতে বিভিন্ন পূর্ণসংখ্যার সংখ্যা ঠিক K হয়। সুতরাং, যদি অ্যারে হয় [1,2,3,1 ,2] এর 3টি ভিন্ন পূর্ণসংখ্যা রয়েছে:1, 2, এবং 3। আমাদের A-এর ভাল সাবয়ারের সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি [1,2,3,1,4] এবং K =3 এর মত হয়, তাহলে আউটপুট হবে 4, কারণ এটি ঠিক চারটি স্বতন্ত্র পূর্ণসংখ্যা সহ তিনটি সাবয়ারে তৈরি করতে পারে, এইগুলি হল [1,2,3 ], [1,2,3,1], [2,3,1], [3,1,4]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• মোস্ট() এ একটি ফাংশন সংজ্ঞায়িত করুন, এটি একটি অ্যারে এবং পরিবর্তনশীল k,

  নেবে

• একটি সেট বর্তমান সংজ্ঞায়িত করুন

• j :=0, উত্তর :=0, n :=a

  এর আকার

• একটি মানচিত্র m

  সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি m[a[i]] শূন্য হয়, m[a[i]] কে 1 দ্বারা বাড়ান -

    • যখন k <0, do −

      • যদি m[a[j]] 1 দ্বারা কমায় এবং m[a[i]] শূন্য হয়, তাহলে −

        • (k 1 দ্বারা বাড়ান)

      • (j 1 দ্বারা বাড়ান)

  • x :=((i - j) + 1)

  • ans :=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