java - 使用握手引理找到具有偶数和的子数组的数量

我试图做练习题，但遇到了一个我不明白背后原因的解决方案。

问题可以在这里找到，找到偶数和子数组的数量。
https://www.geeksforgeeks.org/find-number-subarrays-even-sum/

已经提出了相关的问题，但我特别询问解决方案末尾的握手引理的使用。

我知道我们建立了偶数和奇数子数组的计数，但不明白为什么我们使用握手引理来计算偶数和子数组的数量。如果我们得到偶数和奇数累积和的计数，握手引理如何准确地发挥作用？显然，偶数和子数组由奇数 + 奇数、偶数 + 偶数或孤偶值组成，所以我只想知道在这种特定情况下如何准确地解释所有情况。谢谢你的帮助!

最佳答案

首先我们有一个数字数组，例如:

[1,3,5,2,10,7]

那么，如何计算具有偶数和的子数组的数量？
让我们将其转换为另一个名为 sum 的数组，其中索引 ith 处的值是从 0 到第 i 个索引的子数组的总和

[1,4,9,11,21,28]

显然，我们可以看到，对于 a to b 范围内的子数组，这个子数组的和是偶数当且仅当 sum[b] - sum[a - 1] 是偶数。

现在，让我们想象一个连接 sum 中奇数和奇数条目以及 sum 中的偶数和偶数的图 -> 该图中的边数是这个问题的答案。

因此，根据握手引理，2*E = 所有顶点度的总和

每个奇数顶点的度数为number of odd vertex - 1

每个偶数顶点的度数为number of even vertex - 1

=> 所以

2*E = odd*(odd - 1) + even*(even - 1) => E = odd*(odd - 1)/ 2 + even*(even - 1)/2

理解这一点的另一种方法是对于 odd 条目，选择 odd - odd 对的方法数是 C(odd, 2) = odd*(odd - 1)/2，C 是 combination

关于java - 使用握手引理找到具有偶数和的子数组的数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48495159/