C++の元の配列と同じ合計の個別の要素を持つサブ配列をカウントします

整数を含む配列arr[]が与えられます。目標は、arr []のすべてのサブ配列をカウントして、それぞれの個別の要素の数が元の配列の個別の要素の数と同じになるようにすることです。元の配列が[1,1,2,3]の場合、サブ配列は[1,2,3]と[1,1,2,3]になります。

元の配列の個別の要素の合計は3です。両方のサブ配列の個別の要素の合計も3です

例を挙げて理解しましょう。

入力 − arr [] ={1,2,1,2,3,4,2};

出力 −元の配列と同じ合計の個別の要素を持つサブ配列の数は− 6

説明 − arr []の個別の要素は4（1,2,3,4）です。同じ数の個別の要素を持つサブ配列は次のとおりです:(左から右に個別にカウント）

[1,2,1,2,3,4], [2,1,2,3,4], [1,2,3,4], [1,2,3,4,2], [2,1,2,3,4,2], [1,2,1,2,3,4,2 ]

入力 − arr [] ={8,7,5,6,10};

出力 −元の配列と同じ合計の個別の要素を持つサブ配列の数は− 1

説明 − arr []の個別の要素は5（5,6,7,8,10）です。同じ数の異なる要素を持つサブアレイは次のとおりです:(左から右に異なるカウント）[8,7,6,5,10]。 1つのみ

以下のプログラムで使用されているアプローチは次のとおりです

• 整数の配列arr[]を取り、配列のサイズを計算します。

• 関数sub_ele_diff_one（int arr []、int size）は配列を受け取り、連続する要素が1だけ異なるサブ配列の数を返します。

• 一時変数の数と左右の変数を取得します。

• ランダムペアを作成するために、タイプunordered_mapの変数を取ります。

• ループFORを0から配列のサイズまで開始し、その中でarr[i]の値をunordered_map内に設定します。

• 次に、unordered_mapのサイズを計算し、unordered_mapをクリアします。

• 0から配列のサイズまでループFORを開始します。

• ループ内で、右<サイズと左までWHILEを開始します

• um [arr [right]]

  の値を事前にインクリメントします

• ここで、um [arr [right]] =1かどうかを確認してから、leftの値を1ずつ事前にインクリメントします。

• WHILEの外側では、rightの値を1だけ事前にインクリメントします。

• IF left =unordered_mapのサイズを確認してから、countをcount + size --right+1に設定します

• um[arr[i]]を1デクリメントします

• IF um [arr [i]] =0を確認してから、左を1デクリメントします

• カウントを返す

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
int sub_distinct(int arr[], int size){
   int count = 0, right = 0, left = 0;
   unordered_map<int, int> um;
   for (int i = 0; i < size; ++i){
      um[arr[i]] = 1;
   }
   int um_size = um.size();
   um.clear();
   for(int i = 0; i < size; ++i){
      while (right < size && left < um_size){
         ++um[arr[right]];
         if (um[arr[right]] == 1){
            ++left;
         }
         ++right;
      }
      if (left == um_size){
         count = count + (size - right + 1);
      }
      --um[arr[i]];
      if (um[arr[i]] == 0){
         --left;
      }
   }
   return count;
}
int main(){
   int arr[] = {4, 3, 2, 5};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subarrays having total distinct elements same as original array are: "<<sub_distinct(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of subarrays having total distinct elements same as original array are: 1