# 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

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 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```