计算具有与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的变量来创建随机对。

• 从0开始循环FOR，直到一个数组的大小为止，并在其中设置unordered_map内部的arr [i]值。

• 现在，计算unordered_map的大小并清除unordered_map。

• 从0开始启动FOR循环，直到数组大小为止。

• 在循环内，开始WHILE直到unordered_map的right <size和left <size

• 预增um [arr [right]]的值

• 现在，检查um [arr [right]] = 1，然后将left的值预加1。

• 在WHILE之外，将right的值预加1。

• 检查IF左边= 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