arrays - 查找最长的子数组，其和可被K整除

求和可被k整除的最长子阵。
在O（N）中有可能吗？
如果不是，那么它能做得比n^2好吗？

最佳答案

让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)。

关于arrays - 查找最长的子数组，其和可被K整除，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13089010/