อาร์เรย์ย่อยที่มี K จำนวนเต็มต่างกันใน C++

สมมติว่าเรามีอาร์เรย์ A ที่เป็นจำนวนเต็มบวก เราสามารถเรียกอาร์เรย์ย่อยที่ดี (ต่อเนื่องกัน) ของ 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].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน atMost() ซึ่งจะใช้อาร์เรย์ a และตัวแปร k

• กำหนดหนึ่งชุดปัจจุบัน

• j :=0, ans :=0, n :=ขนาดของ a

• กำหนดหนึ่งแผนที่ m

• สำหรับการเริ่มต้น i :=0, เมื่อ i

  • ถ้า m[a[i]] เป็นศูนย์ ให้เพิ่ม m[a[i]] ขึ้น 1 แล้ว −

    • ในขณะที่ k <0 ทำ -

      • ถ้า 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