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

Question

找到其和能被 K 整除的最长子数组。 在 O(n) 中可能吗？ 如果不能，可以用比 n^2 更好的方式完成吗？

Answer 1

设 s[i] = 前 i 个元素的总和模 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)。