# 3Sum

Given an array `nums` of n integers, are there elements abc in `nums` such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Notice that the solution set must not contain duplicate triplets.

Example 1:

```Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]```

Example 2:

```Input: nums = []
Output: []```

Example 3:

```Input: nums = 
Output: []```

Constraints:

• `0 <= nums.length <= 3000`
• `-105 <= nums[i] <= 105`

This problem is also known as the 3SUM Problem. The 3SUM problem asks if a given set of real numbers contains three elements that sum to zero. The problem cannot be solved better than an O(n2) solution. There are brute force solutions available, that can find all the triplets from an array in O(n3) time. But here we are going to discuss an O(n2) solution using a `HashSet`. Consider the following example:

Note: The solution set must not contain duplicate triplets.

The method signature of the given solution is as follows:

`public static <List> getTriplets(int[] arr)`

So, the method `getTriplets` is taking the input array as an argument and returns a List of List, where each of the inner lists represents a subarray of 3 elements that sum to Zero (Called Triplet here). Following is the pseudo-code for the solution:

We need to find all the subarray from a given array where : (a+b+c) = 0.

```a + b + c = 0
=> c = -a-b
=> c = - (a+b)```

#### Algorithm:

```outer for loop ( i = 0 to i < arr.length)
int a = arr[i];
inner for loop  ( j= (i+1) to j < arr.length)
Set<Integer> set = new HashSet<>();
int b = arr[j];
int c = -(a+b);
if(c is present in the HashSet)
triplet is a,b,c
else

Consider the Following Java implementation:

```import java.util.*;

public class ThreeNumberSumToZero {

public static void main(String[] args) {
int arr[] = {3, -1, -7, -4, -5, 9, 10,-2};
List<List<Integer>> list = getTriplets(arr);
System.out.println(list);
}

public static List<List<Integer>> getTriplets(int[] nums) {

if (nums == null || nums.length < 3) {
return new ArrayList<>();
}

List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int a = nums[i];
Set<Integer> search = new HashSet<>();
for (int j = (i + 1); j < nums.length; j++) {
int b = nums[j];
int c = -(a + b);
if (search.contains(c)) {
List<Integer> triplet = Arrays.asList(a, b, c);
Collections.sort(triplet);
if(!result.contains(triplet)){
}
} else {
}
}
}
return result;
}
}
```

#### Approach 2: Sorting

```class Solution {
public List<List<Integer>> threeSum(int[] nums) {

List<List<Integer>> result = new ArrayList<>();
if(nums == null || nums.length == 0){
return result;
}
int n = nums.length;
Arrays.sort(nums);
Set<String> seen = new HashSet<>();
for(int i = 0 ; i < n ; i++){
int left = nums[i];
int m = i+1;
int r = n-1;
while(m < r){
int mid = nums[m];
int right = nums[r];
int cur_sum = left + mid + right;
if(cur_sum == 0){
String key = left + "_" + mid + "_" + right;
if(!seen.contains(key)){
List<Integer> triplet = new ArrayList<>();
}
m++;
r--;
}else if(cur_sum > 0){
r--;
}else{
m++;
}
}
}
return result;
}
}
```

Categories: Array

Tagged as: , ,