数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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的连续元素的子数组计数。
取一个临时变量count和变量right和left。
取一个无序映射类型变量来创建随机对。
从0到数组大小开始FOR循环，并在其中设置无序映射中的arr[i]值。
现在，计算无序映射的大小并清除无序映射。
从0到数组大小开始FOR循环。
在循环内，直到right < size 和 left < 无序映射大小开始WHILE循环
递增um[arr[right]]的值
现在，检查如果um[arr[right]] = 1，则将left的值递增1。
在WHILE循环外，将right的值递增1。
检查IF left = 无序映射的大小，则将count设置为count + size - right + 1
将um[arr[i]]递减1
检查IF um[arr[i]] = 0，则将left递减1
返回count
打印结果。
示例
#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
182 次浏览
