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

Question

我在尝试做练习题时遇到了一个我不明白其背后原因的解决方案。

题目可以看这里，求偶数和子数组的个数。 https://www.geeksforgeeks.org/find-number-subarrays-even-sum/

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

我知道我们构建了偶数和奇数子数组的计数，但不明白为什么我们使用握手引理来计算偶数和子数组的数量。如果我们得到偶数和奇数累积和的计数，那么握手引理究竟是如何发挥作用的呢？显然，偶数和子数组由奇数 + 奇数、偶数 + 偶数或一个单独的偶数组成，所以我只想知道在这种特定情况下如何准确地考虑所有情况。感谢您的帮助!

Answer 1

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

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

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

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

很明显，我们可以看到对于 a 到 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