使用握手引理查找具有偶数Sum的子数组数 [英] Use of Handshaking Lemma to find number of subarrays with even Sum

问题描述

我正在尝试练习问题，并且遇到了一个我不理解其背后原因的解决方案。

I was attempting to do practice questions and came across a solution I do not understand the reasoning behind.

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

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的子数组数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！