可被k整除的子数组数

  • Z时代
  • 2024-01-10
  • 分类：问答

我在采访中提出了以下问题，尽管我给出了可行的实施方案，但效率不够。

数组A的切片是任意一对整数（P，Q），因此0≤P≤Q <N。如果数字A [P] + A [P +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}

回答：

由于您只对可被K整除的数感兴趣，因此可以对K取模进行所有计算。考虑累积和数组S，使S[i] = S[0] + S[1] + ... +

S[i]。然后（P，Q）是一个可被K iff整除的切片S[P] =

S[Q]（请记住，我们对所有模进行模运算）。因此，您只需要为[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的频率作为前缀和为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）。

以上是 可被k整除的子数组数 的全部内容， 来源链接： utcz.com/qa/407037.html

回到顶部