Các mảng con với K số nguyên khác nhau trong C ++

Giả sử chúng ta có một mảng A gồm các số nguyên dương, chúng ta có thể gọi một mảng con tốt (liền kề) của A, nếu số lượng các số nguyên khác nhau trong mảng con đó chính xác là K. Vì vậy, nếu mảng giống như [1,2,3,1 , 2] có 3 số nguyên khác nhau:1, 2 và 3. Chúng ta phải tìm số mảng con tốt của A.

Vì vậy, nếu đầu vào giống như [1,2,3,1,4] và K =3, thì đầu ra sẽ là 4, vì nó có thể tạo thành ba mảng con với chính xác bốn số nguyên riêng biệt, đây là [1,2,3 ], [1,2,3,1], [2,3,1], [3,1,4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm atMost (), điều này sẽ nhận một mảng a và biến k,
Xác định một tập hợp hiện tại
j:=0, ans:=0, n:=kích thước của a
Xác định một bản đồ m
để khởi tạo i:=0, khi i
- nếu m [a [i]] bằng 0, hãy tăng m [a [i]] lên 1 rồi -
  - trong khi k <0, do -
    - nếu giảm m [a [j]] đi 1 và m [a [i]] bằng 0, thì -
      - (tăng k lên 1)
    - (tăng j lên 1)
- x:=((i - j) + 1)
- ans:=ans + x
trả lại ans
Từ phương thức chính, hãy làm như sau -
trả về atMost (a, k) - atMost (a, k - 1);

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{1,2,3,1,4}, 3

Các mảng con với K số nguyên khác nhau trong C ++

Ví dụ

Đầu vào

Đầu ra