Найти все пары в несортированном массиве, сумма которых составляет divisble на 4

Question

Найти все пары в качестве несортированного массива, сумма которых составляет divisble на 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)