C++の個別の要素サブ配列によって形成されたペアをカウントします

整数要素を含む配列arr[]が与えられます。目標は、arr []のサブ配列の要素によって形成できるペアの数を見つけて、各サブ配列が別個の要素のみを持つようにすることです。配列が[1,2,2,3,3]の場合、個別の要素のみを持つサブ配列は[1,2]と[2,3]になります。また、ペアは（1,2）と（2,3）になるため、ペアの数は2になります。

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

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

出力 −個別の要素サブ配列によって形成されるペアの数は− 6

説明 −異なる要素を持つサブアレイは、[1,2,5、3]、可能なペア（1,2）、（1,3）、（1,5）、（2,5）、（2,3）、 （5,3）

合計6ペア。

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

出力 −個別の要素サブ配列によって形成されるペアの数は− 5

説明 −個別の要素を持つサブアレイは−

[1,2] - pairs: (1,2)
[2,1] - pairs: (2,1)
[1,2,3] - pairs : (1,2), (2,3), (1,3)
Total pairs : 5

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

• 入力として整数配列を取ります。

• 関数distinct_pairs（int arr []、int size）は配列を受け取り、個別の要素サブ配列によって形成されたカウントペアを返します。

• 初期カウントを0とします。変数start=end=0を取ります。

• ベクトルチェック（サイズ、false）を実行して、ウィンドウ内の要素をマークします。

• 開始がサイズ未満になるまでループを開始します

• ループ内で、開始がサイズ未満であり、check [arr [star]] =0になるまで別のループを開始し、カウントをstart --endとして設定し、check [arr [start]]をtrueに設定し、開始を1ずつインクリメントします。

• ループを開始します。終了が開始より小さくなり、開始がサイズに等しくなく、check [arr [start]] =trueの場合、check [arr [end]] =falseに設定し、終了を1つインクリメントします。

• カウントを返す

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
   int count = 0;
   int start = 0;
   int end = 0;
   vector<bool> check(size, false);
   while (start < size){
      while (start < size && !check[arr[start]]){
         count += (start - end);
         check[arr[start]] = true;
         start++;
      }
      while (end < start && (start != size && check[arr[start]])){
         check[arr[end]] = false;
         end++;
      }
   }
   return count;
}
int main(){
   int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
   return 0;
}

出力

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

Count of pairs formed by distinct element sub-arrays are: 17