arrays - 查找未排序数组中的所有对，其总和可被 4 整除

Question

在一个未排序的数组中找到所有对，其总和可以被 4 整除。请推荐一个比 O(n*n) 更好的算法

e.g.

[1,2,4,0,20,22]
k=4
[0,4]
[0,20]
[20,4]
[2,22]

Answer 1

可以在 O(n+k) 中完成，其中 k 是此类对的数量(可以在 O(n^2 ) 本身).

想法是创建 4 个列表，list0,list1,list2,list3，其中 list_i 包含所有元素 x 使得 x%4 ==i。

创建这些列表很简单，在 O(n) 中完成。

一旦你有了这些列表，你所要做的就是获取所有对，其中一个元素来自 list_i，另一个元素位于 list_((4-i)%4) (所以 list0+list0、list1+list3、list2+list2)。这可以非常简单地完成，并且会非常有效地生成所有对。

优化说明:它可以通过根据模数“排序”数组本身来就地完成(非常少的额外空间)，因此您将在数组本身中表示列表。

---

示例:(来自您的列表，修改最少)

array = [1,2,4,0,20,22,7]

生成列表:

list0 = [0,4,20]
list1 = [1]
list2 = [2,22]
list3 = [7]

现在，

"combine" list0 with itself: (0,4), (4,20), (0,20)
"combine" list2 with itself: (2,22)
"combine" list1 with list3: (1,7)