algorithm - 查找范围和等于数组大小的算法

Question

我有一个自然数大小为 n 的数组 A。我需要在 O(n) 中找到 2 个索引的算法：i 和 j，因此子数组 A[i...j] 的总和将除以 n，没有余数。

例如：如果我有这个数组：

5、16、10、3、5、11

总和 10+3+5 = 18 除以 n ( = 6 ) 的大小，没有余数。

我不知道该怎么做，但我知道需要模数组。

有什么建议么？

标签： algorithmdata-structures

Answer 1

用模数存储前缀和数组n，让我们调用这个数组 pref_sum[]

pref_sum[i]将包含A[j]模数的总和n，其中 0 <= j <= i

子数组的总和[i, j]可被nif整除pref_sum[i] - pref_sum[j - 1] modulo n = 0。

所以对于iwith pref_sum[i] = x，我们应该找到 j，其中pref_sum[j - 1] = x。

如果我们将它存储在哈希表或简单数组中，它可以在 O(1) 中找到。