arrays - 如何计算对 (a[i], a[j]), i < j 和 a[i] + a[j] 可以被 k 除以没有余数

Question

如果有可能在少于 O(N^2) 的时间内解决问题，我会徘徊。有长度为N和除数k的数组a。需要计算所有可能的对(a[i], a[j])，例如i < j并且a[i] + a[j]可以被k整除而没有余数。我能得到的只是两个嵌套循环。我可以创建 a[i] 的所有余数除以 k 的数组，但随后需要通过该数组执行类似的嵌套循环，并且它再次为 O(N^2)。

标签： arraysalgorithm

Answer 1

我们可以使用哈希映射在 O(n) 中解决这个问题，其中键是余数，值是我们在迭代时看到这个余数的次数。对于每个数字，在插入第一个数字之后，在插入元素 , 之前A[i]，将键处的值添加到结果中（k - (A[i] mod k)如果它存在于映射中）。然后将 key 处的计数加 1 A[i] mod k。