问题描述
我正在尝试练习问题,并且遇到了一个我不理解其背后原因的解决方案。
I was attempting to do practice questions and came across a solution I do not understand the reasoning behind.
可以在这里找到问题,找到偶数总和子数组。
The question can be found here, finding the number of even sum subarrays.https://www.geeksforgeeks.org/find-number-subarrays-even-sum/
已经询问了相关问题,但我在解决方案结尾特别问有关握手引理的使用
Questions related have been asked, but I am asking specifically about the use of the handshaking lemma at the end of the solution.
我了解我们建立了一个偶数和奇数和子数组的计数,但是不明白为什么我们使用握手引理来计算偶数和子数组的数量。 。如果我们得到的是偶数和奇数的累积和,那么握手引理将如何准确地发挥作用呢?显然,偶数和子数组由奇数+奇数,偶数+偶数或孤立的偶数值组成,因此我只想知道在此特定情况下如何准确地考虑所有情况。谢谢您的帮助!
I understand that we build a count of the even and odd sum subarrays, but do not get why we use the hand shaking lemma to compute the number of even sum subarrays. If we get a count of even and odd cumulative sums, how does the handshaking lemma exactly play into this? Clearly, an even sum subarray is made of either odd + odd, even + even, or a lone even value, so I would just like to know how exactly all cases are being accounted for in this specific scenario. Thanks for your help!
推荐答案
首先,我们有一个数字数组,例如:
First we have an array of numbers, for example:
[1,3,5,2,10,7]
那么,如何计算具有偶数和的子数组的个数?
让我们将其转换为另一个名为 sum
的数组,其中索引 ith
的值是子数组的总和从0到第ith个索引
So, how to count the number of subarray with even sum?Let's convert it into another array called sum
, which the value at index ith
is the sum of subarray from 0 to ith index
[1,4,9,11,21,28]
很明显,对于范围 a到b
的子数组,我们可以看到此子数组的和是偶数,并且仅当 sum [b]-sum [a-1]
是偶数。
Clearly, we can see that for a subarray from range a to b
, the sum of this subarray is even if and only if sum[b] - sum[a - 1]
is even.
现在,让我们想象一下,一个连接在 sum
中的奇数和奇数项与 sum
中的偶数和偶数之间的图形-
Now, let imagine that a graph connecting between odd and odd entry in sum
and even and even in sum
-> the number of edges in this graph is the answer for this problem.
因此,根据握手引理,2 * E =所有顶点度的总和
So, from the handshake lemma, 2*E = sum of all vertexes degree
-
每个奇数顶点的度为
奇数顶点的数量-1
每个偶数顶点的度为偶数顶点的数量-1
=>所以
2*E = odd*(odd - 1) + even*(even - 1) => E = odd*(odd - 1)/ 2 + even*(even - 1)/2
另一种理解方式是对于 odd
条目,选择 odd-奇数
对的方式为 C(奇数,2)=奇数*(奇数-1)/ 2
与C为
Another way to understand this is for odd
entries, the number of ways to choose odd - odd
pairs is C(odd, 2) = odd*(odd - 1)/2
with C is the combination
这篇关于使用握手引理查找具有偶数Sum的子数组数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!