Find three elements in an array that sum to a given value

Objec­tive:  Given an array of integer write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k.

Example:

int a [] = { 3,1,7,4,5,9,10} , k = 21;Output: Elements are 7 4 10 int a [] = { 3,1,7,4,5,9,10} , k = 55;Output: Did not find 3 elements whose sum is 55 

Approach: Brute Force

Use 3 nested loops and find the 3 elements which sum to k.

Time Complexity: O(n^3)

Code:

public class ThreeNumbersSumKBruteForce {
public static void find(int [] a, int k){
for (int i = 0; i <a.length ; i++) {
for (int j = i+1; j <a.length ; j++) {
for (int l = j+1; l <a.length ; l++) {
if(a[i]+a[j]+a[l]==k){
System.out.println("Found 3 elements whose sum is = " +k);
System.out.println("Elements are " + a[i] + " " + a[j]+ " " + a[l]);
return;
}
}
}
}
System.out.println("Did not find 3 elements whose sum is = " +k);
}
public static void main(String[] args) {
int a [] = { 3,1,7,4,5,9,10};
int k = 21;
find(a,k);
}
}

Approach: Sorting

  • Sort the array.
  • Use the other loop to fix the one element at a time
  • Now problem is reduced to “Find a pair of numbers from an array whose sum equals k”

Time Complexity: O(n^2)

Code:

import java.util.Arrays;
public class ThreeNumbersSumKSorting {
public static void find(int [] a, int k){
Arrays.sort(a);
for (int i = 0; i <a.length ; i++) {
int x = a[i];
//now problem is reduced to find two numbers in an array whose sum = M
//here M = k – x and array from index = 1 to end
int M = k x;
int start = i + 1;
int end = a.length1;
while(start<end){
int sum = a[start] + a[end];
if(sum==M){
System.out.println("Found 3 elements whose sum is = " +k);
System.out.println("Elements are " + a[i] + " " + a[start]+ " " + a[end]);
return;
}else if(sum<M)
start++;
else //sum>M
end;
}
}
}
public static void main(String[] args) {
int a [] = { 3,1,7,4,5,9,10};
int k = 21;
find(a,k);
}
}

Approach: Use Hashing

  • Use the other loop to fix the one element at a time.
  • Now required_sum is (with two elements) = k-fixed element.
  • Create a HashSet, Iterate through rest of the array.
  • For current_element, remain_value = required_sum – current_element.
  • Check if remain_value in the HashSet, we have found our triplets else add current_element to the hashset.

Time Complexity: O(n^2)

Code:
https://gist.github.com/thmain/0ec5d9e362e610a5a66cdfde9bfbf9b0

Output:

Found 3 elements whose sum is = 22
Elements are 3 10 9