3 Sum

The 3 sum problem is a famous problem.

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Before solving it, let's first look how it works if we change the problem to finding two numbers which sum up to zero, as follows,

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

The solution is quite straightforward. We use a hash map to keep record what numbers have appeared in the list, then we search the negative of this number in the hash map. If it exists, then we know that these two numbers sum up to zero. The complexity of this algorithm is O(n).

Java: 2 Sum

01 public int[] twoSum(int[] numbers, int target) {
02   int[] results=new int[2];
03   HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
04   for(int i=0; i<numbers.length;i++)
05   {
06     hm.put(numbers[i],i);
07   }
08 
09   for (int i=0;i<numbers.length;i++)
10   {
11     int key= target - numbers [i];
12     if(hm.containsKey(key))
13     {
14       int indx2=hm.get(key);
15       if(i<indx2)
16       {
17         results[0]=i+1;
18         results[1]=indx2+1;
19       }
20     }
21   }
22   return results;
23 }

However, to calculate 3 sum is more tricky. We can still use a hash map or a hash table to store existing values. Then, we need to map the sum of every pairs to the hash table to decide whether the 3 sum triples exist. This will need a complexity of O(n^2).

Is there a better solution?

Another method introduced by wiki is to do a sorting first.
http://en.wikipedia.org/wiki/3SUM

You first do a sorting using O(nlogn), then you have two nested loops to traverse the array, which still cost O(n^2). The sorting method is still not fast enough, the large test case cannot pass the OJ.

We should think about how theses three numbers might be. Think about many situations.

1. What if there are more than three of zeros? Then we should output<0,0,0>
2. If there is one 0, and if there exists a and -a, then we should output<-a,0,a>
3. a, b are two positive numbers, c is a negative number
4. a, b are two negative numbers, c is a positive number

In the following approach, we use two hash tables, one for positive numbers, one for negative numbers. Further, we use a counter to store the number of zeros. The algorithm is also O(n^2), however, as we do not   need to compute the sum of every pair, it use less time than the above methods. O(n^2/2)<O(n^2/8)*2.

Java: 3 Sum

001 public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
002   ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
003   ArrayList<Integer>posArray=new ArrayList<Integer>();
004   ArrayList<Integer>negArray=new ArrayList<Integer>();
005   Hashtable <Integer,Integer> pos = new Hashtable<Integer,Integer>();
006   Hashtable <Integer,Integer> neg = new Hashtable<Integer,Integer>();
007   int numZeros=0;
008 
009   for(int i=0;i<num.length;i++)
010   {
011     if(num[i]==0)
012     {
013       numZeros++;
014     }
015     else if(num[i]<0)
016     {
017       if(!neg.containsKey(num[i]))
018       {
019         neg.put(num[i],1);
020       }
021       else
022       {
023         int time=neg.get(num[i]);
024         time++;
025         neg.put(num[i],time);
026       }
027       if(!negArray.contains(num[i]))
028       {
029         negArray.add(num[i]);
030       }
031     }
032     else //num[i]>0
033     {
034       if(!pos.containsKey(num[i]))
035       {
036         pos.put(num[i],1);
037       }
038       else
039       {
040         int time=pos.get(num[i]);
041         time++;
042         pos.put(num[i],time);
043       }
044       if(!posArray.contains(num[i]))
045       {
046         posArray.add(num[i]);
047       }
048     }
049   }
050 
051   if(numZeros>=3)
052   {
053     ArrayList<Integer>tripple=new ArrayList<Integer>();
054     for(int i=0;i<3;i++)
055       tripple.add(0);
056     result.add(tripple);
057   }
058   if(numZeros>=1)
059   {
060     for(int i=0;i<negArray.size();i++)
061     {
062       int negValue=negArray.get(i);
063       int posValue=0-negValue;
064       if(pos.containsKey(posValue))
065       {
066         ArrayList<Integer>tripple=new ArrayList<Integer>();
067         tripple.add(negValue);
068         tripple.add(0);
069         tripple.add(posValue);
070         result.add(tripple);
071       }
072     }
073   }
074 
075   for(int i=0;i<negArray.size();i++)
076   {
077     int negValue=negArray.get(i);
078     if(neg.get(negValue)>=2)
079     {
080       int posValue=negValue*(-2);
081       if(pos.containsKey(posValue))
082       {
083         ArrayList<Integer>tripple=new ArrayList<Integer>();
084         tripple.add(negValue);
085         tripple.add(negValue);
086         tripple.add(posValue);
087         result.add(tripple);
088       }
089     }      
090   }
091 
092   for(int i=0;i<posArray.size();i++)
093   {
094     int posValue=posArray.get(i);
095     if(pos.get(posValue)>=2)
096     {
097       int negValue=posValue*(-2);    
098       if(neg.containsKey(negValue))
099       {
100         ArrayList<Integer>tripple=new ArrayList<Integer>();
101         tripple.add(negValue);
102         tripple.add(posValue);
103         tripple.add(posValue);
104         result.add(tripple);
105       }
106     }
107   
108   }
109 
110   for(int i=0;i<negArray.size();i++)
111   {
112     for(int j=i+1;j<negArray.size();j++)
113     {
114       int small=negArray.get(i);
115       int large=negArray.get(j);
116     
117       if(small>large)
118       {
119       
120         small=negArray.get(j);
121         large=negArray.get(i);
122       }
123       int sum=small+large;
124       int posValue=0-sum;
125       if(pos.containsKey(posValue))
126       {
127       
128         ArrayList<Integer>tripple=new ArrayList<Integer>();
129         tripple.add(small);
130         tripple.add(large);
131         tripple.add(posValue);
132         result.add(tripple);
133       }
134     
135     }
136   }
137 
138   for(int i=0;i<posArray.size();i++)
139   {
140     for(int j=i+1;j<posArray.size();j++)
141     {
142       int small=posArray.get(i);
143       int large=posArray.get(j);
144     
145       if(small>large)
146       {
147       
148         small=posArray.get(j);
149         large=posArray.get(i);
150       }
151       int sum=small+large;
152       int negValue=0-sum;
153       if(neg.containsKey(negValue))
154       {
155       
156         ArrayList<Integer>tripple=new ArrayList<Integer>();
157         tripple.add(negValue);
158         tripple.add(small);
159         tripple.add(large);
160       
161         result.add(tripple);
162       }
163     
164     }
165   }
166 
167   return result;
168 }