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

Question

如果可以在小于O(N^2)的范围内解决这个问题，我会四处游走。有长度为N的数组a和除数因子k，需要计数所有可能的对( ai，aj)，例如i

Answer 1

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

Answer 2

对ai mod k上的数组进行排序。这是在时间O(N日志N)中完成的。

用两个索引扫描数组，从左到右和从右到左，这样就可以检测到元素的序列，使和mod k为0，并将这些序列的长度乘以。这是在时间O(N)中完成的。

例如用k=5

2, 9, 21, 13, 1, 8, 22, 6 

分拣后，

1, 21, 6, 22, 2, 13, 8, 9
1   1  1   2  2   3  3  4

序列是

||1, 21, 6|2, 22|13, 8|9|
||1   1  1|2   2| 3  3|4|

因此，3x1 + 2x2对。

您需要一些额外的技巧来避免计算对i≥j。例如，您可以在数组中的每个元素中追加它的初始索引，然后按字典顺序对值mod k进行排序，然后在索引上排序。然后，在计数对时，通过一种合并过程，可以枚举有效的对。总复杂度仍为O(N)。

2, 9, 21, 13, 1, 8, 22, 6
0  1   2   3  4  5   6  7

分拣后，

21, 1, 6, 2, 22, 13, 8, 9
 1  1  1  2   2   3  3  4
 2  4  7  0   6   3  5  1

序列是

||21, 1, 6|2, 22|13, 8|9|
|| 1  1  1|2   2| 3  3|4|
|| 2  4  7|0   6| 3  5|1|

现在要计算来自|2, 22|13, 8|的有效对，我们看到2后面跟着13, 8，22后面没有什么，因此有2+0有效对。

Answer 3

创建一桶从0到k-1的剩馀物。现在用除数k除以每个数组，并根据除以k后产生的余数，将该数放入剩余桶中。现在创建这样的一对-

每一个产生余数的数1都可以与所有产生余数的k - 1成对，因为它们的和将被k完全除以(没有余数)。

类似地，剩余2桶中的数字将与剩余k - 2桶中的数字成对。这样做是为了i<=j。

此外，剩余0桶中的所有数字将在它们之间形成对。

时间复杂度是O(n)，空间复杂度是O(k) (对于剩余的桶)。

编辑：

如果只需要计数对的数量，那么剩余的桶可以像一个简单的数组(其所有元素由0初始化)，并且每个元素在特定的索引处都将包含数组中产生的与该索引等效的元素数。做简单的计算--剩余桶索引1处的数字乘以剩余桶索引k - 1处的数字，索引2处的数字乘以索引k - 2处的数字，等等(i<=j)。此外，在索引0中计算可能的对数。把它们加起来，这就给出了答案。