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] and N[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 until i == j
• Compute the sum of N[i] + N[j]
• If sum > -x => j-- => continue the loop
• If sum < -x => i++ => continue the loop
• If sum == -x => count++, either increase i or decrease j, continue the loop

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;
}