计算由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）接收数组，并返回由不同元素子数组形成的Count对。

• 初始计数为0。变量start = end = 0。

• 进行矢量检查（大小，false）以标记窗口中的元素。

• 启动循环，直到启动小于大小

• 在循环内部，开始另一个循环，直到开始小于大小且check [arr [star]] = 0，然后将count设置为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