找到最长的子阵列,其总和可被K整除

Question

找到最长的子阵列,其总和可被K整除.在O(n)中有可能吗？如果没有,它可以更好地完成n ^ 2？

Answer 1

我们s[i] = sum of first i elements modulo K.

我们有:

s[i] = (s[i - 1] + a[i]) % K

我们必须为每一个找到i最小的j那样s[i] == s[j].您可以通过散列s[i]值来找到它.如果K很小,你可以保留一个数组p[i] = first position for which s[k] == i.

复杂性是O(n).