小编ant*_*obg的帖子

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

数组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}