2-Sum
Problem Statement
Given a set of \(N\) integers, find how many pairs sum to 0.
Brute Force
Sum all pairs and count whichever sum to 0. This is \(O(N^{2})\).
Sort & Search
First sort all the numbers in \(O(N\log N)\) time. Then loop through your sorted list. For each integer, we want to see if its negative is in the list. A simple binary search will give it to you.
3-Sum
Problem Statement
Given a set of \(N\) integers, find how many triplets sum to 0.
Brute Force
Sum all triplets and count whichever sum to 0. This is \(O(N^{3})\).
Sort & Search
First sort all the numbers in \(O(N\log N)\) time. Then loop through your sorted list. For each pair of integers, we want to see if the required third integer exists in the list. A simple binary search will give it to you.
This is \(O(N^{2}\log N)\).
\(O(N^{2})\)
First sort all the numbers in \(O(N\log N)\) time. Then loop through the list. For each element \(a\), we want to know if \(b\) and \(c\) exist such that \(-a=b+c\). This can be done in linear time: Start traversing the list from the left and assign the number to \(b\). We know the desired \(c\). Start searching for \(c\) by traversing from the right.
For the next \(b\), we continue searching for \(c\) from the right from our previous stopping point. We can do this as the list is sorted. This way we find all instances of \(-a=b+c\) in linear time with fixed \(a\).
Overall, this is \(O(N^{2})\).