数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中统计具有相同偶数和奇数元素的子数组
给定一个正整数数组。目标是在数组中找到数字的子数组，使得每个子数组都具有相同数量的偶数和奇数元素。如果数组是 { 1,2,3,4 }，则子数组将是 {1,2}，{2,3}，{3,4}，{1,2,3,4}。此类子数组的数量为 4。
让我们通过例子来理解
输入 − arr[] = {1,3,5,7,8,3,2 };
输出 − 具有相同偶数和奇数元素的子数组数量为 − 4
解释 − 子数组将是 − { 7,8 }，{8,3} {3,2}，{7,8,3,2}
输入 − arr[] = {2,4,6 };
输出 − 具有相同偶数和奇数元素的子数组数量为 − 0
解释 − 所有元素都是偶数。
下面程序中使用的算法如下
在这种方法中，我们将使用一个变量temp作为数组元素之间的差值（最初为0），如果arr[i]是奇数则将其加1，如果arr[i]是偶数则将其减1。当temp的值重复时，则必须存在一个子数组，其在这些索引之间具有相同数量的偶数和奇数。temp可以是正数也可以是负数。取两个哈希数组arr_1[size+1]用于正差值的频率，arr_2[size+1]用于负差值的频率。
对于每个差值temp<0，将arr_1[-temp]中的频率添加到计数中。[-(-temp)]给出一个正索引。
对于每个差值temp>0，将arr_2[temp]中的频率添加到计数中。由于相同差值的所有出现都将是子数组的一部分。将这些频率更新为1。
Arr[] = { 1,3,5,7,8,3,2 }从0开始的Temp值 −
1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } //all differences are positive
arr_2[] { 0,0,0,0,0,0,0,0 } //no difference is negative
Adding arr_1[temp] to count in each iteration gives count=4.子数组是 − { 7,8 }，{8,3} {3,2}，{7,8,3,2}
将初始数组作为arr[]。
函数Sub_even_odd(int arr[], int size)接受数组及其长度并返回具有相同偶数和奇数元素的子数组的数量。
将初始计数设置为0，并将变量temp设置为一个变量，当遇到奇数值时递增，当遇到偶数值时递减。
取两个数组arr_1[]和arr_2[]来存储temp的频率。arr_1[]用于temp的正值，如果整个数组都是偶数，则最多可以达到size+1。
arr_2[]用于temp的负值，如果整个数组都是偶数，则最多可以达到size+1。
使用for循环遍历arr[]。
如果arr[i] & 1==1，这意味着arr[i]是奇数。递增temp。否则递减temp。
如果temp<0，则将arr_2[]中的相应频率添加到计数中。将该频率加1。
如果temp>0，则将arr_1[]中的相应频率添加到计数中。将该频率加1。
最后，我们计算了arr[]中具有相同数量的偶数和奇数元素的子数组的数量
返回计数作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size){
int count = 0;
int temp = 0;
int arr_1[size + 1] = {0};
int arr_2[size + 1] = {0};
arr_1[0] = 1;
for (int i = 0; i < size; i++){
if(arr[i] & 1 == 1)
{ temp++; }
else
{ temp--; }
if (temp < 0){
count += arr_2[-temp];
arr_2[-temp]++;
}
else{
count += arr_1[temp];
arr_1[temp]++;
}
}
return count;
}
int main(){
int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays with same even and odd elements are: "<<Sub_even_odd(arr,
size);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of subarrays with same even and odd elements are: 4
380 次浏览
