C++でK個の異なる整数を持つサブ配列

正の整数の配列Aがあるとすると、そのサブ配列内の異なる整数の数が正確にKである場合、Aの適切なサブ配列（連続）を呼び出すことができます。したがって、配列が[1,2,3,1 、2]には、1、2、3の3つの異なる整数があります。Aの適切なサブ配列の数を見つける必要があります。

したがって、入力が[1,2,3,1,4]のようで、K =3の場合、出力は4になります。これは、正確に4つの異なる整数を持つ3つのサブ配列を形成できるため、これらは[1,2,3 ]、[1,2,3,1]、[2,3,1]、[3,1,4]。

これを解決するには、次の手順に従います-

• 関数atMost（）を定義します。これは、配列aと変数kを取ります。

• 1セットの電流を定義する

• j：=0、ans：=0、n：=aのサイズ

• 1つのマップを定義する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

• ansを返す

• メインの方法から、次のようにします-

• 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