我在采访中提出了以下问题，尽管我给出了可行的实施方案，但效率不够。
数组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中出现的次数。
S[i] = S[0] + S[1] + ... + S[i]
S[P] = S[Q]
这是一些伪代码：
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
它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）。
( ( x - 1 ) * ( ( x - 1 ) + 1 ) / 2
