给定一个数组 arr[] 大小 N 仅包含0和1。问题是计算0和1数量相等的子阵列。
null
例如：
Input : arr[] = {1, 0, 0, 1, 0, 1, 1}Output : 8The index range for the 8 sub-arrays are:(0, 1), (2, 3), (0, 3), (3, 4), (4, 5)(2, 5), (0, 5), (1, 6)
这个问题与环境密切相关 最大的子阵列，0和1的数量相等。 方法： 以下是步骤：
- 把ARR []中的0个都看成是1。
- 创建一个哈希表，其中包含每个 总和[i] 值，其中sum[i]=sum（arr[0]+..+arr[i]），对于i=0到n-1。
- 现在开始计算累积和，然后我们得到该和的增量计数1，表示为哈希表中的索引。在累积和中具有相同值的每对位置的数组构成一个连续范围，具有相等数量的1和0。
- 现在遍历哈希表并获得哈希表中每个元素的频率。让频率表示为 频率 .每人 频率 >1我们可以通过以下方式选择子数组的任意两对索引： （频率*（频率–1））/2 很多方法。对所有人都一样 频率 加起来，结果将是所有可能的子数组的数量，其中包含相等数量的1和0。
- 另外，添加 频率 将0的和添加到哈希表中，以获得最终结果。
说明： 考虑到所有的0都是-1，如果sum[i]==sum[j]，其中sum[i]=sum（arr[0]+..+arr[i]）和sum[j]=sum（arr[0]+..+arr[j]）并且’i’小于’j’，那么sum（arr[i+1]+..+arr[j]）必须是0。只有当arr（i+1，…，j）包含相等数量的1和0时，它才能为0。
C++
// C++ implementation to count subarrays with // equal number of 1's and 0's #include <bits/stdc++.h> using namespace std; // function to count subarrays with // equal number of 1's and 0's int countSubarrWithEqualZeroAndOne( int arr[], int n) { // 'um' implemented as hash table to store // frequency of values obtained through // cumulative sum unordered_map< int , int > um; int curr_sum = 0; // Traverse original array and compute cumulative // sum and increase count by 1 for this sum // in 'um'. Adds '-1' when arr[i] == 0 for ( int i = 0; i < n; i++) { curr_sum += (arr[i] == 0) ? -1 : arr[i]; um[curr_sum]++; } int count = 0; // traverse the hash table 'um' for ( auto itr = um.begin(); itr != um.end(); itr++) { // If there are more than one prefix subarrays // with a particular sum if (itr->second > 1) count += ((itr->second * (itr->second - 1)) / 2); } // add the subarrays starting from 1st element and // have equal number of 1's and 0's if (um.find(0) != um.end()) count += um[0]; // required count of subarrays return count; } // Driver program to test above int main() { int arr[] = { 1, 0, 0, 1, 0, 1, 1 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "Count = " << countSubarrWithEqualZeroAndOne(arr, n); return 0; } |
JAVA
// Java implementation to count subarrays with // equal number of 1's and 0's import java.util.*; class GFG { // function to count subarrays with // equal number of 1's and 0's static int countSubarrWithEqualZeroAndOne( int arr[], int n) { // 'um' implemented as hash table to store // frequency of values obtained through // cumulative sum Map<Integer,Integer> um = new HashMap<>(); int curr_sum = 0 ; // Traverse original array and compute cumulative // sum and increase count by 1 for this sum // in 'um'. Adds '-1' when arr[i] == 0 for ( int i = 0 ; i < n; i++) { curr_sum += (arr[i] == 0 ) ? - 1 : arr[i]; um.put(curr_sum, um.get(curr_sum)== null ? 1 :um.get(curr_sum)+ 1 ); } int count = 0 ; // traverse the hash table 'um' for (Map.Entry<Integer,Integer> itr : um.entrySet()) { // If there are more than one prefix subarrays // with a particular sum if (itr.getValue() > 1 ) count += ((itr.getValue()* (itr.getValue()- 1 )) / 2 ); } // add the subarrays starting from 1st element and // have equal number of 1's and 0's if (um.containsKey( 0 )) count += um.get( 0 ); // required count of subarrays return count; } // Driver program to test above public static void main(String[] args) { int arr[] = { 1 , 0 , 0 , 1 , 0 , 1 , 1 }; int n = arr.length; System.out.println( "Count = " + countSubarrWithEqualZeroAndOne(arr, n)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to count # subarrays with equal number # of 1's and 0's # function to count subarrays with # equal number of 1's and 0's def countSubarrWithEqualZeroAndOne (arr, n): # 'um' implemented as hash table # to store frequency of values # obtained through cumulative sum um = dict () curr_sum = 0 # Traverse original array and compute # cumulative sum and increase count # by 1 for this sum in 'um'. # Adds '-1' when arr[i] == 0 for i in range (n): curr_sum + = ( - 1 if (arr[i] = = 0 ) else arr[i]) if um.get(curr_sum): um[curr_sum] + = 1 else : um[curr_sum] = 1 count = 0 # traverse the hash table 'um' for itr in um: # If there are more than one # prefix subarrays with a # particular sum if um[itr] > 1 : count + = ((um[itr] * int (um[itr] - 1 )) / 2 ) # add the subarrays starting from # 1st element and have equal # number of 1's and 0's if um.get( 0 ): count + = um[ 0 ] # required count of subarrays return int (count) # Driver code to test above arr = [ 1 , 0 , 0 , 1 , 0 , 1 , 1 ] n = len (arr) print ( "Count =" , countSubarrWithEqualZeroAndOne(arr, n)) # This code is contributed by "Sharad_Bhardwaj". |
C#
// C# implementation to count subarrays // with equal number of 1's and 0's using System; using System.Collections.Generic; class GFG { // function to count subarrays with // equal number of 1's and 0's static int countSubarrWithEqualZeroAndOne( int []arr, int n) { // 'um' implemented as hash table to store // frequency of values obtained through // cumulative sum Dictionary< int , int > mp = new Dictionary< int , int >(); int curr_sum = 0; // Traverse original array and compute cumulative // sum and increase count by 1 for this sum // in 'um'. Adds '-1' when arr[i] == 0 for ( int i = 0; i < n; i++) { curr_sum += (arr[i] == 0) ? -1 : arr[i]; if (mp.ContainsKey(curr_sum)) { var v = mp[curr_sum]; mp.Remove(curr_sum); mp.Add(curr_sum, ++v); } else mp.Add(curr_sum, 1); } int count = 0; // traverse the hash table 'um' foreach (KeyValuePair< int , int > itr in mp) { // If there are more than one prefix subarrays // with a particular sum if (itr.Value > 1) count += ((itr.Value* (itr.Value - 1)) / 2); } // add the subarrays starting from 1st element // and have equal number of 1's and 0's if (mp.ContainsKey(0)) count += mp[0]; // required count of subarrays return count; } // Driver program to test above public static void Main(String[] args) { int []arr = { 1, 0, 0, 1, 0, 1, 1 }; int n = arr.Length; Console.WriteLine( "Count = " + countSubarrWithEqualZeroAndOne(arr, n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation to count subarrays with // equal number of 1's and 0's // function to count subarrays with // equal number of 1's and 0's function countSubarrWithEqualZeroAndOne(arr, n) { // 'um' implemented as hash table to store // frequency of values obtained through // cumulative sum var um = new Map(); var curr_sum = 0; // Traverse original array and compute cumulative // sum and increase count by 1 for this sum // in 'um'. Adds '-1' when arr[i] == 0 for ( var i = 0; i < n; i++) { curr_sum += (arr[i] == 0) ? -1 : arr[i]; if (um.has(curr_sum)) um.set(curr_sum, um.get(curr_sum)+1); else um.set(curr_sum, 1) } var count = 0; // traverse the hash table 'um' um.forEach((value, key) => { // If there are more than one prefix subarrays // with a particular sum if (value > 1) count += ((value * (value - 1)) / 2); }); // add the subarrays starting from 1st element and // have equal number of 1's and 0's if (um.has(0)) count += um.get(0); // required count of subarrays return count; } // Driver program to test above var arr = [1, 0, 0, 1, 0, 1, 1]; var n = arr.length; document.write( "Count = " + countSubarrWithEqualZeroAndOne(arr, n)); // This code is contributed by noob2000. </script> |
输出：
Count = 8
时间复杂性： O（n）。 辅助空间： O（n）。
另一种方法：
C++
#include <bits/stdc++.h> using namespace std; int countSubarrWithEqualZeroAndOne( int arr[], int n) { map< int , int > mp; int sum = 0; int count = 0; for ( int i = 0; i < n; i++) { // Replacing 0's in array with -1 if (arr[i] == 0) arr[i] = -1; sum += arr[i]; // If sum = 0, it implies number of 0's and 1's are // equal from arr[0]..arr[i] if (sum == 0) count++; //if mp[sum] exists then add "frequency-1" to count if (mp[sum]) count += mp[sum]; //if frequency of "sum" is zero then we initialize that frequency to 1 //if its not 0, we increment it if (mp[sum] == 0) mp[sum] = 1; else mp[sum]++; } return count; } int main() { int arr[] = { 1, 0, 0, 1, 0, 1, 1 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "count=" << countSubarrWithEqualZeroAndOne(arr, n); } |
JAVA
import java.util.HashMap; import java.util.Map; // Java implementation to count subarrays with // equal number of 1's and 0's public class Main { // Function that returns count of sub arrays // with equal numbers of 1's and 0's static int countSubarrWithEqualZeroAndOne( int [] arr, int n) { Map<Integer, Integer> myMap = new HashMap<>(); int sum = 0 ; int count = 0 ; for ( int i = 0 ; i < n; i++) { // Replacing 0's in array with -1 if (arr[i] == 0 ) arr[i] = - 1 ; sum += arr[i]; // If sum = 0, it implies number of 0's and 1's // are equal from arr[0]..arr[i] if (sum == 0 ) count++; if (myMap.containsKey(sum)) count += myMap.get(sum); if (!myMap.containsKey(sum)) myMap.put(sum, 1 ); else myMap.put(sum, myMap.get(sum) + 1 ); } return count; } // main function public static void main(String[] args) { int arr[] = { 1 , 0 , 0 , 1 , 0 , 1 , 1 }; int n = arr.length; System.out.println( "Count = " + countSubarrWithEqualZeroAndOne(arr, n)); } } |
Python3
# Python3 implementation to count subarrays # with equal number of 1's and 0's def countSubarrWithEqualZeroAndOne(arr, n): mp = dict () Sum = 0 count = 0 for i in range (n): # Replacing 0's in array with -1 if (arr[i] = = 0 ): arr[i] = - 1 Sum + = arr[i] # If Sum = 0, it implies number of # 0's and 1's are equal from arr[0]..arr[i] if ( Sum = = 0 ): count + = 1 if ( Sum in mp.keys()): count + = mp[ Sum ] mp[ Sum ] = mp.get( Sum , 0 ) + 1 return count # Driver Code arr = [ 1 , 0 , 0 , 1 , 0 , 1 , 1 ] n = len (arr) print ( "count =" , countSubarrWithEqualZeroAndOne(arr, n)) # This code is contributed by mohit kumar |
C#
// C# implementation to count subarrays with // equal number of 1's and 0's using System; using System.Collections.Generic; class GFG { // Function that returns count of sub arrays // with equal numbers of 1's and 0's static int countSubarrWithEqualZeroAndOne( int [] arr, int n) { Dictionary< int , int > myMap = new Dictionary< int , int >(); int sum = 0; int count = 0; for ( int i = 0; i < n; i++) { // Replacing 0's in array with -1 if (arr[i] == 0) arr[i] = -1; sum += arr[i]; // If sum = 0, it implies number of 0's and 1's // are equal from arr[0]..arr[i] if (sum == 0) count++; if (myMap.ContainsKey(sum)) count += myMap[sum]; if (!myMap.ContainsKey(sum)) myMap.Add(sum, 1); else { var v = myMap[sum] + 1; myMap.Remove(sum); myMap.Add(sum, v); } } return count; } // Driver code public static void Main(String[] args) { int [] arr = { 1, 0, 0, 1, 0, 1, 1 }; int n = arr.Length; Console.WriteLine( "Count = " + countSubarrWithEqualZeroAndOne(arr, n)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation to count subarrays with // equal number of 1's and 0's function countSubarrWithEqualZeroAndOne(arr, n) { var mp = new Map(); var sum = 0; let count = 0; for ( var i = 0; i < n; i++) { //Replacing 0's in array with -1 if (arr[i] == 0) arr[i] = -1; sum += arr[i]; //If sum = 0, it implies number of 0's and 1's are //equal from arr[0]..arr[i] if (sum == 0) count += 1; if (mp.has(sum) == true ) count += mp.get(sum); if (mp.has(sum) == false ) mp.set(sum, 1); else mp.set(sum, mp.get(sum)+1); } return count; } // Driver program to test above var arr = [1, 0, 0, 1, 0, 1, 1]; var n = arr.length; document.write( "Count = " + countSubarrWithEqualZeroAndOne(arr, n)); // This code is contributed by noob2000. </script> |
输出：
Count = 8
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
