# Find three elements in an array that sum to a zero.

Objec­tive:  Given an array of integers write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0.

Example

```int [] = { 3,-1,-7,-4,-5,9,10};
Elements are -4 9 -5```

Approach: Brute Force

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

Time Complexity: O(n^3)

Code:

 public class ThreeNumbersSumZeroBruteForce { public static void find(int [] a){ for (int i = 0; i

Approach: Sorting

Time Complexity: O(n^2)

Code:

 import java.util.Arrays; public class ThreeNumbersSumZeroSorting { //need to find a + b + c = 0 //OR we can reduce the problem to b + c = -a public static void find(int [] x){ Arrays.sort(x); for (int i = 0; i sum end—; } } } public static void main(String[] args) { int a [] = { 3,–1,–7,–4,–5,9,10}; find(a); } }

Approach: Use Hashing

• Use the other loop to fix the one element at a time.
• Now required_sum is (with two elements) = -fixed element.
• Create a HashSet, Iterate through the 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:

 import java.util.HashSet; public class ThreeNumbersSumZeroHashing { //we need to find a + b + c = 0 //OR reduce the problem c = -(a+b) public static void find(int [] x){ for (int i = 0; i set = new HashSet(); for (int j=i+1; j

Output:

```Found 3 elements whose sum is = 0
Elements are -4 9 -5
```

### 1 thought on “Find three elements in an array that sum to a zero.”

1. Improvement 1:
Loop at line number 8 can be improved to execute till i < x.length – 1

Improvement 2:
Return statement at line number 18 should be removed to find other possible triplets in the array