Given an array and a value, find all the triplets in the array whose sum is equal to the given value. For example, if the given array is
{12, 3, 4, 1, 6, 9}
and the given sum is24
, then this is one triplet(12, 3 and 9)
which contributes to the total sum of 24.Solution for given example:
6, 9, 9
6, 6, 12
3, 9, 12
The ordering of the numbers in the solution does not matter.
Duplicate triplet is not allowed.
A number is not allowed to be used multiple time.
Here is my code:
package kata.array;
import java.util.*;
public class ThreeSum {
static class Triplet {
int x, y, z;
public Triplet(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
@Override
public int hashCode() {
return Objects.hash(x, y, z);
}
@Override
public boolean equals(Object o) {
if (o instanceof Triplet) {
Set<Integer> numbers = new HashSet<>();
numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));
Triplet other = (Triplet) o;
return numbers.containsAll(new ArrayList<>(Arrays.asList(other.x, other.y, other.z)));
}
return false;
}
}
public static Set<Triplet> findTriplets(int numbers[], int targetSum) {
Set<Triplet> triplets = new HashSet<>();
// insert all pairs in the look up table
Map<Integer, int[]> lookup = new HashMap<>();
for (int i = 0; i < numbers.length - 1; i++) {
for (int j = i + 1; j < numbers.length; j++) {
int total = numbers[i] + numbers[j];
lookup.put(total, new int[]{i, j});
}
}
// look for the complement, if found viola! here you go with the matching triplet
for (int number : numbers) {
int complement = targetSum - number;
if (lookup.containsKey(complement)) {
int indexes[] = lookup.get(complement);
int x = numbers[indexes[0]], y = numbers[indexes[1]];
triplets.add(new Triplet(x, y, number));
}
}
return triplets;
}
}
To run this code:
public void findTriplets() throws Exception {
int numbers[] = {12, 3, 4, 1, 6, 9};
System.out.print(ThreeSum.findTriplets(numbers, 24));
for (ThreeSum.Triplet triplet : ThreeSum.findTriplets(numbers, 24)) {
System.out.println(triplet.x + ", " + triplet.y + ", " + triplet.z);
}
// can handle duplicate?
System.out.println("==============================");
numbers = new int[] {12, 3, 4, 1, 6, 9, 9, 9, 9, 9};
System.out.print(ThreeSum.findTriplets(numbers, 24));
for (ThreeSum.Triplet triplet : ThreeSum.findTriplets(numbers, 24)) {
System.out.println(triplet.x + ", " + triplet.y + ", " + triplet.z);
}
}