C++で指定された2つの要素の出現回数が等しいサブ配列をカウントします

整数の配列arr[]が与えられます。また、2つの数値AとB。目標は、AとBの出現がすべて等しくなるようにarr[]のすべてのサブ配列をカウントすることです。配列が[1,2,3]で、Aが1、Bが2の場合、サブ配列は[3]、[1,2]、[1,2,3]になります。

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

入力 − arr [] ={2、2、1、1、1、5}; A =1、B =5

出力 −等しい数のサブアレイの数。与えられた2つの要素の出現回数は-4

説明 −サブアレイは− [2]、[2]、[2,2]、[1,5]になります。最初の3つには1と5が0回出現し、最後の1つには両方が1回出現します。

入力 − arr [] ={5,3,7,5,3}; A =1、B =2

出力 −等しい数のサブアレイの数。与えられた2つの要素の出現回数は-15

説明 −サブアレーは−（1と2が0回出現する）

[5], [3], [7], [5], [3] - 5
[5,3], [3,7], [7,5], [5,3] - 4
[5,3,7], [3,7,5], [7,5,3] - 3
[5,3,7,5], [3,7,5,3] - 2
[5,3,5,7,5] - 1

1と2の両方が発生しない（0回の発生）合計15個のサブアレイ。

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

2つのforループを使用して配列をトラバースし、可能なすべてのサブ配列を生成します。 i=0からi<=size-1およびj=iからj<=size-1まで。形成されるサブアレイは、arr[i]からarr[j]の間にあります。各サブアレイのAとBの頻度を数えます。等しい場合は、カウントを増やします。

• 数字の配列arr[]を取ります。

• 関数sub_EqualOccurrence（int arr []、int size、int A、int B）は配列を受け取り、等しい数のサブ配列の数を返します。 AとBの。

• 初期カウントを0とします。

• i=0からi<=size-1およびj=0からj<=size-1までの2つのforループを使用して配列をトラバースします。

• サブ配列arr[i]からarr[j]のAとBの数について、2つの変数total_A、total_Bを0とします。

• arr [j]をAおよびBと比較します。arr[j]がAまたはBの場合、それぞれのカウントをインクリメントします（total_Aまたはtotal_B）。

• total_A==total_Bの場合。インクリメントカウント。 （サブアレイには、要素と同じ数のAとBがあります）。

• 両方のループの終わりに、結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int sub_EqualOccurrence(int arr[], int size, int A, int B){
   int count = 0;
   for (int i = 0; i <= size - 1; i++){
      int total_A = 0;
      int total_B = 0;
      for (int j = i; j <= size - 1; j++){
         if (arr[j] == A){
            total_A++;
         }
         else if (arr[j] == B){
            total_B++;
         }
         if(total_A == total_B){
            count++;
         }
      }
   }
   return count;
}
// Driver code
int main(){
   int arr[] = { 2, 3, 1, 1, 4, 5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   int A = 1, B = 5;
   cout<<"Count of subarrays with equal number of occurrences of two given elements are: "<<sub_EqualOccurrence(arr, size, A, B);
   return (0);
}

出力

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

Count of subarrays with equal number of occurrences of two given elements are: 5