Найти количество пар в массиве, между которыми сумма элементов равна 0

Question

Недавно я столкнулся с вопросом, который говорит, что нам нужно найти количество пар в массиве между (включая оба конца), сумма элементов которых равна 0. Например: int[] arr = {1,-2,3,0,-2,2}. Тогда парами, между которыми сумма элементов равна 0, являются (3,5), (4,5), (0,4). Таким образом, ответ = 3. Есть ли способ, которым мы можем решить это в O (n).

Answer 1

Трюк, который вам нужен для этого, состоит в том, чтобы создать массив кумулятивных сумм, так что sums[i] = sum of all arr[0] through arr[i].

Конечно, если sums[i] == 0, то (0,i) является одной из пар, которые вы ' ищите, и вы должны посчитать это.

Для всех остальных, обратите внимание, что если сумма arr[i] though arr[j] равна нулю, то sums[i-1] == sums[j].

Так что вам просто нужно знать, сколько совпадающих пар значений есть в sums.

Составить карту ха sh из значения-> число, которое дает частоту каждого значения в sums. Затем для каждого счета m, который по крайней мере 2, у вас есть m*(m-1)/2 пар.