Three Sum Problem

A three sum problem is one in which sum of 3 numbers from a given inter array is zero.Find all pairs from the given array of n size along with the algorithm complexity.

A[i]+A[j]+A[k]=0

Approach

1) Sort the array

2) Loop i from 1 to n.

3)Initialize j to i and k to n-1

4)while k>j:do

• sum = a[i]+a[j]+a[k]
• if sum greater than zero increment j
• else decrement k

 Complexity :-O(n²)

For Eg:-
In JAVA,
The source code for ThreeSum problem will be:-

package com.collection.collection_ex; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashSet; import java.util.Set; public class ThreeSum { static Set<ArrayList<Integer>> l=new HashSet<ArrayList<Integer>>(); public static void main(String args[]) { int[] array = {2,7,6,-7,0,8,-3,-5,-1,7,-7,14}; System.out.println(threeSum(array)); System.out.println(threeSum(array).size()); } public static Set<ArrayList<Integer>> threeSum(int[] array) {    if(array == null) return null;    int n = array.length;    if(n < 3) return null;    Arrays.sort(array);    int count = 0;    for(int i = 0; i < n - 1; i++) {        int j = i ;        int k = n - 1;        while(k >j) {         count++;            int sum = array[i] + array[j] + array[k];            if(sum == 0)            {             ArrayList<Integer> s = new ArrayList<Integer>();                      s.add(array[i]);                      s.add(array[j]);                      s.add(array[k]);                      Collections.sort(s);                      l.add(s);            }                        if(sum < 0) j++; else k--;        }    }    return l; } }