Given an sorted array of integers, I want to find the number of pairs that sum to $0$. For example, given $\{-3,-2,0,2,3,4\}$, the number of pairs sum to zero is $2$.
Let $N$ be the number of elements in the input array. If I use binary search to find the additive inverse for an element in the array, the order is $O(\log N)$. If I traverse all the elements in the set, then the order is $O(N\log N)$.
How to find an algorithm which is of order $O(N)$?
Let $A$ be the sorted input array. Keep two pointers $l$ and $r$ that go through the elements in $A$. The pointer $l$ will go through the "left part" of $A$, that is the negative integers. The pointer $r$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $0 \notin A$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $A$.
COUNT-PAIRS(A[1..N]):
l = index of the last negative integer in A
r = index of the first positive integer in A
count = 0;
while(l >= 0 and r <= N)
if(A[l] + A[r] == 0)
++count; ++right; --left; continue;
if(A[r] > -1 * A[l])
--left;
else
++right;
It is obvious the algorithm takes $O(N)$ time.
The simplest approach, by my understanding, seems to be to use a Hash-Table, H = {a[0] = true, .. , a[n-1] = true}. This Hash-Table can be built in O(n) time. Once the Hash-Table is built, iterate through A[0,..,n-1] and check if H[-1*a[i]] exists. If it does, increment a counter by 1, and return the final result. This is clearly O(n).
Note that we can lookup a value in a Python set in constant time.
def twoSum(data):
count = 0
nums = set()
for num in data:
if (num * -1) in nums:
count += 1
nums.add(num)
return count
