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)$?
How to develop an $O(N)$ algorithm solve the 2-sum problem?
algorithms
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.