查找其总和除以给定数字的数组子数组的数量

查找其总和除以给定数字的数组子数组的数量

对于给定的数字

X

…

基本思想：（ 带有非正式的正确性证明）

如果范围内的数字总和

[a, b]

可被整除

X

，则：

(∑i=1 to a-1input[i]) % X = (∑i=1 to binput[i]) % X

用较少的数学术语来说：

the sum from the first element to b = the sum from the first element to a   + the sum of the elements between the two

所以：

the sum of the elements between the two = the sum from the first element to b       - the sum from the first element to a

然后，如果右边的那些和在除以时都具有相同的余数

X

，则余数将被抵消，并且在两者之间的元素之和将被整除

X

。详细说明：

C = the sum of the elements between the twoB = the sum from the first element to bA = the sum from the first element to a

现在，我们可以转换

B

到窗体

PX + Q

和

A

到窗体

RX + S

，对于一些整数

P

，

Q

，

R

并

S

与

0 <= Q, S <X

。在此，通过定义，

Q

和

S

将各自的余数

B

和

A

通过被划分

X

。

然后我们有：

C = (PX + Q) - (RX + S)C = PX + Q - RX - SC = PX - RX + Q - SC = (P-R)X + Q - S

显然

(P-R)X

可以被

X

（可以简单地

(P-R)

）整除。现在我们只需要

Q - S

被整除

X

，但是由于

0 <= Q, S <X

，它们需要相等。

例：

让

B = 13

，

A = 7

，

X = 3

。

在这里

B % X = 1

和

A % X = 1

。

我们可以将

B

as

4*3 + 1

和

A

as 重写

2*3 + 1

。

然后

C = 4*3 + 1 - 2*3 - 1 = 2*3

，可以将其整除

3

。

高级方法：

构造一个的哈希图

key -> value

，其中每个值代表您可以从数组的开始处开始到在给定位置处所累加的总数的方式

sum mod X =key

（请参见“ Mod 3”行以及下面示例中的映射值） ）。

现在，根据上述逻辑，我们知道，如果两个子数组分别从开始位置

a

和结束位置开始，并且

b

分别具有相同的

sum mod X

子数组，

[a,b]

则它们可以被整除

X

。

因此，哈希图中的每个值代表一组可能的起点和终点的大小，这将使我们

X

可以被除以一个子数组（任何点都可以是起点或终点）。

选择这些起点和终点的可能方法很简单

value choose 2 =value!/(2*(value-2)!)

（如果值为1，则为0）。

因此，我们为哈希图中的每个值计算该值，并将它们全部加起来以得到可被整除的子数组的数量

X

。

算法：

构造一个哈希图，该哈希图将存储到目前为止所有数字的累加总和，以

mod X

映射到剩余值出现的频率（按预期构造

O(n)

）。

将

0

的值增加一-这对应于数组的开始。

将计数初始化为0。

对于哈希图中的每个值，将其添加

value!/(2*(value-2)!)

到计数中。

该计数是所需的值。

运行时间：

期望的

O(n)

。

例：

Input:    0  5  3  8  2  1X = 3Sum:   0  0  5  8 16 18 19Mod 3: 0  0  2  2  1  0  1Map:  0 -> 3  1 -> 2  2 -> 2Count = 3! / 2*(3-2)! = 3  +        2! / 2*(2-2)! = 1  +        2! / 2*(2-2)! = 1      = 5

子数组将是：

0  5  3  8  2  1-          0      =  0 % 3 = 0-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0      -    3      =  3 % 3 = 0 ----      2 + 1  =  3 % 3 = 0