Nothing special here. It’s just a blog post for summarising my algorithm learning course.
1. The 3-sum problem
The 3-sum problem is described as below
Given N distinct integers, how many triples sum to exactly zero?
2. Brute-force - N3 solution
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++)
if (a[i] + a[j] + a[k] == 0)
count++;
Do NOT use this
3. N2logN solution
- Sort the input array N
- For each pair of numbers
N[i]
andN[j]
, binary search for the value-(N[i] + N[j])
- If exist, count that combination of 3 numbers as 1 3-sum
Complexity
Get pair of number | Binary Search | Total |
N2 | logN | N2logN |
Pseudo code
function binarySearch(N, val) {
//... detailed implementation goes here
// complexity 0(logN)
}
function threeSum(N) {
var count = 0;
for (i = 0; i < N.length; i++) {
for (j = i+1; j < N.length; j++) {
val = 0 - (N[i] + N[j]);
if (binarySearch(N, val)) {
count++;
}
}
}
return count;
}
4. N2 solution
- Sort the input array N
- For each item in the array N
- Try to find 2 item in the array such that
N[i] + N[j] == -x
- Initialize
count = 0
- Loop from the beginning (
i
) and end (j
) of the array, for each loop untili == j
- Compute the
sum
ofN[i] + N[j]
- If
sum > -x
=>j--
=> continue the loop - If
sum < -x
=>i++
=> continue the loop - If
sum == -x
=>count++
, either increasei
or decreasej
, continue the loop
- Compute the
- Try to find 2 item in the array such that
Complexity
Only 1 loop inside another loop, the total complexity is N2
Pseudo code
function threeSum(N) {
let count = 0;
for(let i = 0; i < N.length; i++) {
let x = N[i];
let minusX = 0 - x;
let i = 0, j = N - 1;
while (i !== j) {
const sum = N[i] + N[j];
if (sum === minusX) {
count++;
i++;
} else if (sum > minusX) {
j--;
} else {
i++;
}
}
}
return count;
}