给定一个数组，求其和为偶数的子数组数。
null
例子：
Input : arr[] = {1, 2, 2, 3, 4, 1} Output : 9There are possible subarrays with evensum. The subarrays are 1) {1, 2, 2, 3} Sum = 82) {1, 2, 2, 3, 4} Sum = 123) {2} Sum = 2 (At index 1)4) {2, 2} Sum = 45) {2, 2, 3, 4, 1} Sum = 126) {2} Sum = 2 (At index 2)7) {2, 3, 4, 1} Sum = 108) {3, 4, 1} Sum = 89) {4} Sum = 4
O（n） 2. )时间和O（1）空间法[蛮力] 我们可以简单地生成所有可能的子数组，并找出其中所有元素的和是否为偶数。如果它是偶数，那么我们将计算该子数组，否则忽略它。
C++
/* C++ program to count number of sub-arrays whose sum is even using brute force Time Complexity - O(N^2) Space Complexity - O(1) */ #include<iostream> using namespace std; int countEvenSum( int arr[], int n) { int result = 0; // Find sum of all subarrays and increment // result if sum is even for ( int i=0; i<=n-1; i++) { int sum = 0; for ( int j=i; j<=n-1; j++) { sum = sum + arr[j]; if (sum % 2 == 0) result++; } } return (result); } // Driver code int main() { int arr[] = {1, 2, 2, 3, 4, 1}; int n = sizeof (arr) / sizeof (arr[0]); cout << "The Number of Subarrays with even" " sum is " << countEvenSum (arr, n); return (0); } |
JAVA
// Java program to count number // of sub-arrays whose sum is // even using brute force // Time Complexity - O(N^2) // Space Complexity - O(1) import java.io.*; class GFG { static int countEvenSum( int arr[], int n) { int result = 0 ; // Find sum of all subarrays // and increment result if // sum is even for ( int i = 0 ; i <= n - 1 ; i++) { int sum = 0 ; for ( int j = i; j <= n - 1 ; j++) { sum = sum + arr[j]; if (sum % 2 == 0 ) result++; } } return (result); } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 2 , 3 , 4 , 1 }; int n = arr.length; System.out.print( "The Number of Subarrays" + " with even sum is " ); System.out.println(countEvenSum(arr, n)); } } // This code is contributed by ajit |
Python3
# Python 3 program to count number # of sub-arrays whose sum is even # using brute force # Time Complexity - O(N^2) # Space Complexity - O(1) def countEvenSum(arr, n): result = 0 # Find sum of all subarrays and # increment result if sum is even for i in range ( 0 , n, 1 ): sum = 0 for j in range (i, n, 1 ): sum = sum + arr[j] if ( sum % 2 = = 0 ): result = result + 1 return (result) # Driver code if __name__ = = '__main__' : arr = [ 1 , 2 , 2 , 3 , 4 , 1 ] n = len (arr) print ( "The Number of Subarrays" , "with even sum is" , countEvenSum (arr, n)) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to count number // of sub-arrays whose sum is // even using brute force // Time Complexity - O(N^2) // Space Complexity - O(1) using System; class GFG { static int countEvenSum( int []arr, int n) { int result = 0; // Find sum of all subarrays // and increment result if // sum is even for ( int i = 0; i <= n - 1; i++) { int sum = 0; for ( int j = i; j <= n - 1; j++) { sum = sum + arr[j]; if (sum % 2 == 0) result++; } } return (result); } // Driver code static public void Main () { int []arr = {1, 2, 2, 3, 4, 1}; int n = arr.Length; Console.Write( "The Number of Subarrays" + " with even sum is " ); Console.WriteLine(countEvenSum(arr, n)); } } // This code is contributed by m_kit |
PHP
<?php // PHP program to count number // of sub-arrays whose sum is // even using brute force // Time Complexity - O(N^2) // Space Complexity - O(1) function countEvenSum( $arr , $n ) { $result = 0; // Find sum of all subarrays // and increment result if // sum is even for ( $i = 0; $i <= $n - 1; $i ++) { $sum = 0; for ( $j = $i ; $j <= $n - 1; $j ++) { $sum = $sum + $arr [ $j ]; if ( $sum % 2 == 0) $result ++; } } return ( $result ); } // Driver code $arr = array (1, 2, 2, 3, 4, 1); $n = sizeof ( $arr ); echo "The Number of Subarrays " , "with even sum is " , countEvenSum ( $arr , $n ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to count number // of sub-arrays whose sum is // even using brute force // Time Complexity - O(N^2) // Space Complexity - O(1) function countEvenSum(arr, n) { let result = 0; // Find sum of all subarrays // and increment result if // sum is even for (let i = 0; i <= n - 1; i++) { let sum = 0; for (let j = i; j <= n - 1; j++) { sum = sum + arr[j]; if (sum % 2 == 0) result++; } } return (result); } // Driver Code let arr = [1, 2, 2, 3, 4, 1]; let n = arr.length; document.write( "The Number of Subarrays" + " with even sum is " ); document.write(countEvenSum(arr, n)); </script> |
输出
The Number of Subarrays with even sum is 9
O（n）时间和O（1）空间方法[有效] 如果我们计算输入数组的temp[]中的累积和数组，那么我们可以看到从i开始到j结束的子数组在temp[]如果（temp[j]–temp[i]）%2=0时有一个偶数和。因此，我们不构建累积和数组，而是构建一个累积和模2数组，并使用握手公式计算0和1在temp[]数组中出现的次数。[n*（n-1）/2]
C++
/* C++ program to count number of sub-arrays with even sum using an efficient algorithm Time Complexity - O(N) Space Complexity - O(1)*/ #include<iostream> using namespace std; int countEvenSum( int arr[], int n) { // A temporary array of size 2. temp[0] is // going to store count of even subarrays // and temp[1] count of odd. // temp[0] is initialized as 1 because there // a single even element is also counted as // a subarray int temp[2] = {1, 0}; // Initialize count. sum is sum of elements // under modulo 2 and ending with arr[i]. int result = 0, sum = 0; // i'th iteration computes sum of arr[0..i] // under modulo 2 and increments even/odd count // according to sum's value for ( int i=0; i<=n-1; i++) { // 2 is added to handle negative numbers sum = ( (sum + arr[i]) % 2 + 2) % 2; // Increment even/odd count temp[sum]++; } // Use handshake lemma to count even subarrays // (Note that an even can be formed by two even // or two odd) result = result + (temp[0]*(temp[0]-1)/2); result = result + (temp[1]*(temp[1]-1)/2); return (result); } // Driver code int main() { int arr[] = {1, 2, 2, 3, 4, 1}; int n = sizeof (arr) / sizeof (arr[0]); cout << "The Number of Subarrays with even" " sum is " << countEvenSum (arr, n); return (0); } |
JAVA
// Java program to count // number of sub-arrays // with even sum using an // efficient algorithm // Time Complexity - O(N) // Space Complexity - O(1) import java.io.*; class GFG { static int countEvenSum( int arr[], int n) { // A temporary array of size 2. // temp[0] is going to store // count of even subarrays // and temp[1] count of odd. // temp[0] is initialized as // 1 because there a single even // element is also counted as // a subarray int temp[] = { 1 , 0 }; // Initialize count. sum is // sum of elements under modulo // 2 and ending with arr[i]. int result = 0 , sum = 0 ; // i'th iteration computes sum // of arr[0..i] under modulo 2 // and increments even/odd count // according to sum's value for ( int i = 0 ; i <= n - 1 ; i++) { // 2 is added to handle // negative numbers sum = ((sum + arr[i]) % 2 + 2 ) % 2 ; // Increment even/odd count temp[sum]++; } // Use handshake lemma to // count even subarrays // (Note that an even can // be formed by two even // or two odd) result = result + (temp[ 0 ] * (temp[ 0 ] - 1 ) / 2 ); result = result + (temp[ 1 ] * (temp[ 1 ] - 1 ) / 2 ); return (result); } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 2 , 3 , 4 , 1 }; int n = arr.length; System.out.println( "The Number of Subarrays" + " with even sum is " + countEvenSum (arr, n)); } } // This code is contributed by ajit |
Python 3
# Python 3 program to count number of sub-arrays # with even sum using an efficient algorithm # Time Complexity - O(N) # Space Complexity - O(1) def countEvenSum(arr, n): # A temporary array of size 2. temp[0] is # going to store count of even subarrays # and temp[1] count of odd. # temp[0] is initialized as 1 because there # a single even element is also counted as # a subarray temp = [ 1 , 0 ] # Initialize count. sum is sum of elements # under modulo 2 and ending with arr[i]. result = 0 sum = 0 # i'th iteration computes sum of arr[0..i] # under modulo 2 and increments even/odd # count according to sum's value for i in range ( n): # 2 is added to handle negative numbers sum = ( ( sum + arr[i]) % 2 + 2 ) % 2 # Increment even/odd count temp[ sum ] + = 1 # Use handshake lemma to count even subarrays # (Note that an even can be formed by two even # or two odd) result = result + (temp[ 0 ] * (temp[ 0 ] - 1 ) / / 2 ) result = result + (temp[ 1 ] * (temp[ 1 ] - 1 ) / / 2 ) return (result) # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 2 , 3 , 4 , 1 ] n = len (arr) print ( "The Number of Subarrays with even" " sum is" , countEvenSum (arr, n)) # This code is contributed by ita_c |
C#
// C# program to count // number of sub-arrays // with even sum using an // efficient algorithm // Time Complexity - O(N) // Space Complexity - O(1) using System; class GFG { static int countEvenSum( int []arr, int n) { // A temporary array of size 2. // temp[0] is going to store // count of even subarrays // and temp[1] count of odd. // temp[0] is initialized as // 1 because there a single even // element is also counted as // a subarray int []temp = {1, 0}; // Initialize count. sum is // sum of elements under modulo // 2 and ending with arr[i]. int result = 0, sum = 0; // i'th iteration computes sum // of arr[0..i] under modulo 2 // and increments even/odd count // according to sum's value for ( int i = 0; i <= n - 1; i++) { // 2 is added to handle // negative numbers sum = ((sum + arr[i]) % 2 + 2) % 2; // Increment even // or odd count temp[sum]++; } // Use handshake lemma to // count even subarrays // (Note that an even can // be formed by two even // or two odd) result = result + (temp[0] * (temp[0] - 1) / 2); result = result + (temp[1] * (temp[1] - 1) / 2); return (result); } // Driver code static public void Main () { int []arr = {1, 2, 2, 3, 4, 1}; int n = arr.Length; Console.WriteLine( "The Number of Subarrays" + " with even sum is " + countEvenSum (arr, n)); } } // This code is contributed // by akt_mit |
PHP
<?php // PHP program to count number // of sub-arrays with even sum // using an efficient algorithm // Time Complexity - O(N) // Space Complexity - O(1)*/ function countEvenSum( $arr , $n ) { // A temporary array of size 2. // temp[0] is going to store // count of even subarrays and // temp[1] count of odd. temp[0] // is initialized as 1 because // there a single even element // is also counted as a subarray $temp = array (1, 0); // Initialize count. sum is // sum of elements under // modulo 2 and ending with arr[i]. $result = 0; $sum = 0; // i'th iteration computes // sum of arr[0..i] under // modulo 2 and increments // even/odd count according // to sum's value for ( $i = 0; $i <= $n - 1; $i ++) { // 2 is added to handle // negative numbers $sum = (( $sum + $arr [ $i ]) % 2 + 2) % 2; // Increment even/odd // count $temp [ $sum ]++; } // Use handshake lemma to // count even subarrays // (Note that an even can // be formed by two even // or two odd) $result = $result + (int)( $temp [0] * ( $temp [0] - 1) / 2); $result = $result + (int)( $temp [1] * ( $temp [1] - 1) / 2); return ( $result ); } // Driver code $arr = array (1, 2, 2, 3, 4, 1); $n = sizeof ( $arr ); echo "The Number of Subarrays " . "with even" , " sum is " , countEvenSum ( $arr , $n ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to count // number of sub-arrays // with even sum using an // efficient algorithm // Time Complexity - O(N) // Space Complexity - O(1) function countEvenSum(arr,n) { // A temporary array of size 2. // temp[0] is going to store // count of even subarrays // and temp[1] count of odd. // temp[0] is initialized as // 1 because there a single even // element is also counted as // a subarray let temp = [1, 0]; // Initialize count. sum is // sum of elements under modulo // 2 and ending with arr[i]. let result = 0, sum = 0; // i'th iteration computes sum // of arr[0..i] under modulo 2 // and increments even/odd count // according to sum's value for (let i = 0; i <= n - 1; i++) { // 2 is added to handle // negative numbers sum = ((sum + arr[i]) % 2 + 2) % 2; // Increment even/odd count temp[sum]++; } // Use handshake lemma to // count even subarrays // (Note that an even can // be formed by two even // or two odd) result = result + (temp[0] * (temp[0] - 1) / 2); result = result + (temp[1] * (temp[1] - 1) / 2); return (result); } // Driver code let arr=[1, 2, 2, 3, 4, 1]; let n = arr.length; document.write( "The Number of Subarrays" + " with even sum is " + countEvenSum (arr, n)); // This code is contributed by rag2127 </script> |
输出：
The Number of Subarrays with even sum is 9
O（n）时间和O（1）空间法（自下而上法）
如果我们从上一个索引开始计数，并从当前索引开始跟踪到目前为止具有偶数和的子数组的数量，那么我们可以从上一个索引开始计算具有偶数和的子数组的数量
C++
/* C++ program to count number of sub-arrays with even sum using an efficient algorithm Time Complexity - O(N) Space Complexity - O(1)*/ #include <iostream> using namespace std; long long countEvenSum( int a[], int n) { // Result may be large enough not to // fit in int; long long res = 0; // To keep track of subarrays with even sum // starting from index i; int s = 0; for ( int i = n - 1; i >= 0; i--) { if (a[i] % 2 == 1) { /* s is the count of subarrays starting from * index i+1 whose sum was even*/ /* If a[i] is odd then all subarrays starting from index i+1 which was odd becomes even when a[i] gets added to it. */ s = n - i - 1 - s; } else { /* If a[i] is even then all subarrays starting from index i+1 which was even remains even and one extra a[i] even subarray gets added to it. */ s = s + 1; } res = res + s; } return res; } // Driver Code int main() { int arr[] = { 1, 2, 2, 3, 4, 1 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "The Number of Subarrays with even" " sum is " << countEvenSum(arr, n); return 0; } // This code is contributed by Aditya Anand |
JAVA
// Java program to count // number of sub-arrays // with even sum using an // efficient algorithm // Time Complexity - O(N) // Space Complexity - O(1) import java.io.*; class GFG { public static long countEvenSum( int a[], int n) { // result may be large enough not to // fit in int; long res = 0 ; // to keep track of subarrays with even // sum starting from index i int s = 0 ; for ( int i = n - 1 ; i >= 0 ; i--) { if (a[i] % 2 == 1 ) { // s is the count of subarrays starting from // index i+1 whose sum was even /*if a[i] is odd then all subarrays starting from index i+1 which was odd becomeseven when a[i] gets added to it.*/ s = n - i - 1 - s; } else { /*if a[i] is even then all subarrays starting from index i+1 which was even remainseven and one extra a[i] even subarray gets added to it.*/ s = s + 1 ; } res = res + s; } return res; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 2 , 3 , 4 , 1 }; int n = arr.length; System.out.println( "The Number of Subarrays" + " with even sum is " + countEvenSum(arr, n)); } } // This code is contributed by Aditya Anand |
Python3
# Python 3 program to count number of sub-arrays # with even sum using an efficient algorithm # Time Complexity - O(N) # Space Complexity - O(1) def countEvenSum(arr, n): # result may be large # enough not to fit in int; res = 0 # to keep track of subarrays # with even sum starting from index i s = 0 for i in reversed ( range (n)): if arr[i] % 2 = = 1 : # s is the count of subarrays # starting from index i+1 # whose sum was even """ if a[i] is odd then all subarrays starting from index i+1 which was odd becomes even when a[i] gets added to it. """ s = n - i - 1 - s else : """ if a[i] is even then all subarrays starting from index i+1 which was even remains even and one extra a[i] even subarray gets added to it. """ s = s + 1 res = res + s return res # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 2 , 3 , 4 , 1 ] n = len (arr) print ( "The Number of Subarrays with even" " sum is" , countEvenSum(arr, n)) # This code is contributed by Aditya Anand |
C#
// C# program to count // number of sub-arrays // with even sum using an // efficient algorithm // Time Complexity - O(N) // Space Complexity - O(1) using System; public class GFG { public static long countEvenSum( int [] a, int n) { // result may be large enough not to // fit in int; long res = 0; // to keep track of subarrays with even // sum starting from index i int s = 0; for ( int i = n - 1; i >= 0; i--) { if (a[i] % 2 == 1) { // s is the count of subarrays starting from // index i+1 whose sum was even /*if a[i] is odd then all subarrays starting from index i+1 which was odd becomeseven when a[i] gets added to it.*/ s = n - i - 1 - s; } else { /*if a[i] is even then all subarrays starting from index i+1 which was even remainseven and one extra a[i] even subarray gets added to it.*/ s = s + 1; } res = res + s; } return res; } // Driver Code static public void Main () { int [] arr = { 1, 2, 2, 3, 4, 1 }; int n = arr.Length; Console.WriteLine( "The Number of Subarrays" + " with even sum is " + countEvenSum(arr, n)); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program to count // number of sub-arrays // with even sum using an // efficient algorithm // Time Complexity - O(N) // Space Complexity - O(1) function countEvenSum(a, n) { // result may be large enough not to // fit in int; let res = 0; // to keep track of subarrays with even // sum starting from index i let s = 0; for (let i = n - 1; i >= 0; i--) { if (a[i] % 2 == 1) { // s is the count of subarrays starting from // index i+1 whose sum was even /*if a[i] is odd then all subarrays starting from index i+1 which was odd becomeseven when a[i] gets added to it.*/ s = n - i - 1 - s; } else { /*if a[i] is even then all subarrays starting from index i+1 which was even remainseven and one extra a[i] even subarray gets added to it.*/ s = s + 1; } res = res + s; } return res; } let arr = [ 1, 2, 2, 3, 4, 1 ]; let n = arr.length; document.write( "The Number of Subarrays" + " with even sum is " + countEvenSum(arr, n)); </script> |
输出
The Number of Subarrays with even sum is 9
本文由 拉希特·贝尔瓦里亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
