可被k整除的子数组的数量

Question

我在接受采访时遇到了以下问题,尽管我提供了一个有效的实施方案,但效率还不够高.

数组A的切片是任意一对整数(P,Q),使得0≤P≤Q<N.如果数字A [P] + A [P,则数组A的切片(P,Q)可被K整除+1] + ... + A [Q-1] + A [Q]可被K整除.

要求我写的函数必须返回被K整除的切片数.预期的时间复杂度为O(max(N,K)),空间复杂度为O(K).

我的解决方案是最简单的,一个循环在另一个内部并检查每个切片:O(n ^ 2)

我一直在想,但我真的无法弄清楚如何在O(max(N,K))中做到这一点.

它可能是子集求和问题的变体,但我不知道如何计算每个子数组.

编辑:数组中的元素可能是否定的.这是一个例子:

A = {4, 5, 0, -2, -3, 1}, K = 5

Function must return 7, because there are 7 subarrays which sums are divisible by 5
{4, 5, 0, -2, -3, 1}
{5}
{5, 0}
{5, 0, -2, -3}
{0}
{0, -2, -3}
{-2, -3}

Answer 1

正如你只关心数字整除K,你可以做所有的计算模K.考虑累积和数组S这样S[i] = S[0] + S[1] + ... + S[i].然后(P,Q)是可被K iff整除的切片S[P] = S[Q](记住我们以K 为模进行所有计算).因此,您只需计算[0,...,K-1]的每个可能值,它在S中出现的次数.

这是一些伪代码:

B = new array( K )
B[0]++
s = 0
for i = 0 to N - 1
  s = ( s + A[i] ) % K
  B[s]++
ans = 0
for i = 0 to K - 1
  ans = ans + B[i] * ( B[i] - 1 ) / 2

一旦你知道它们是S中具有值i的x单元,你想要计算具有值i的单元格中的开始的切片数量,并且在具有值i的单元格中结束,这个数字是x ( x - 1 ) / 2.为了解决边缘问题,我们添加一个值为0的单元格.

x ( x - 1 ) / 2代表什么:让我们假设我们的数组是[4,5,0],频率为4,因为前缀sum是x,在这种情况下是3.现在我们可以从x的值得出结论,至少有x-1个数字可以被k整除或者mod k等于0.现在这些x-1数字中可能的总数是1 + 2 + 3 ...... +(x - 1)是( ( x - 1 ) * ( ( x - 1 ) + 1 ) / 2.(从1到N的求和的标准公式,其中N代表(x-1).

Answer 2

对于给定的数字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 two
B = the sum from the first element to b
A = 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 - S
C = PX - RX + Q - S
C = (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为4*3 + 1和A作为2*3 + 1。

然后C = 4*3 + 1 - 2*3 - 1 = 2*3，可以将其整除3。

高级方法：

构造一个哈希图，该哈希图将存储到目前为止所有数字的累加总和，以mod X映射到剩余值出现的频率（按预期构建O(n)）。

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

将计数初始化为0。

遍历哈希图并将nC2（= value!/(2*(value-2)!)）添加到计数中。在2我们在这里选择的是子数组的起始和结束位置。

该计数是所需的值。

运行时间：

期望的O(n)。

例：

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
  0 -> 3
  2 -> 2
  1 -> 2

Count = 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