3Sum
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)
Naive Way:这已经是我第三次做这道题了。 brute force是O(n^3)，然后较好的做法是O(n^2)。
经查证，还没有方法能在小于O(n^2)的时间内解决3sum问题。实际在OJ上做，发现即使是同样的O(n^2)
的run time, 也会有超时。
第一种做法, 一开始不排序，先用一个map记录每个数的出现次数，遍历O(n^2)求两两之和，再再map中
看看有没有剩下的那个数，这样的做法需要在形成list的时候排序，并且得有一个set控制duplicate。
但是这样的做法超时了。
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
Set<List<Integer>> set = new HashSet<List<Integer>>();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
List<List<Integer>> output = new ArrayList<List<Integer>>();
for(int i = 0;i < num.length;i++){
if(map.containsKey(num[i]))
map.put(num[i], map.get(num[i])+1);
else
map.put(num[i], 1);
}
for(int i = 0;i < num.length-1;i++){
for(int j = i+1;j < num.length;j++){
int a = num[i];
int b = num[j];
int c = -num[i]-num[j];
if(map.containsKey(c)){
int count = 1;
count += a==c?1:0;
count += b==c?1:0;
if(count <= map.get(c)){
List<Integer> list = new ArrayList<Integer>();
int arr[] = new int[3];
arr[0] = a;
arr[1] = b;
arr[2] = c;
Arrays.sort(arr);
list.add(arr[0]);
list.add(arr[1]);
list.add(arr[2]);
if(!set.contains(list))
set.add(list);
}
}
}
}
output.addAll(set);
return output;
}
}
Improved Way:
第二种做法，也是比较牛一点的做法，就是wiki上给的做法，但是这里要求去除重复，要做出修改。
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
List<List<Integer>> rlst = new ArrayList<List<Integer>>();
Arrays.sort(num);
for(int u = 0;u < num.length-2;u++){
if(u==0 || (u > 0 && num[u]!=num[u-1])){
int i = u+1;
int j = num.length-1;
while(i < j){
int sum = num[i]+num[j]+num[u];
if(sum==0){
List<Integer> list = new ArrayList<Integer>();
list.add(num[u]);
list.add(num[i]);
list.add(num[j]);
rlst.add(list);
while(i < j){
if(num[j]!=num[j-1])
break;
j--;
}
while(i < j){
if(num[i]!=num[i+1])
break;
i++;
}
i++;
j--;
}else if(sum > 0){
j--;
}else{
i++;
}
}
}
}
return rlst;
}
}
最后我发现我第一次的做法，是可以通过的O(n^2)非常非常的厉害，我觉得，居然想到了用正数负数。
public class Solution {
List<List<Integer>> output;
HashSet<List<Integer>> visited;
public List<List<Integer>> threeSum(int[] num) {
output = new ArrayList<List<Integer>>();
visited = new HashSet<List<Integer>>();
//Arrays.sort(num);
Map<Integer, Integer> positive = new HashMap<Integer, Integer>();
Map<Integer, Integer> negative = new HashMap<Integer, Integer>();
int numOfZeros = 0;
// construct the mapping
for(int i = 0;i < num.length;i++){
if(num[i] == 0)
numOfZeros++;
if(num[i] > 0)
if(positive.containsKey(num[i]))
positive.put(num[i], positive.get(num[i])+1);
else
positive.put(num[i],1);
if(num[i] < 0)
if(negative.containsKey(num[i]))
negative.put(num[i], negative.get(num[i])+1);
else
negative.put(num[i],1);
}
// generate results
// two positive + one negative
for(Map.Entry<Integer, Integer> a:positive.entrySet())
for(Map.Entry<Integer, Integer> b:positive.entrySet())
if(a.getKey() != b.getKey() || a.getValue() >= 2)
if(negative.containsKey(-a.getKey()-b.getKey()))
addResult(a.getKey(),b.getKey(),-a.getKey()-b.getKey());
// two negative + one positive
for(Map.Entry<Integer, Integer> a:negative.entrySet())
for(Map.Entry<Integer, Integer> b:negative.entrySet())
if(a.getKey() != b.getKey() || a.getValue() >= 2)
if(positive.containsKey(-a.getKey()-b.getKey()))
addResult(a.getKey(),b.getKey(),-a.getKey()-b.getKey());
// one positive+zero+one negative
if(numOfZeros > 0)
for(Map.Entry<Integer, Integer> a:negative.entrySet())
if(positive.containsKey(-a.getKey()))
addResult(0,a.getKey(),-a.getKey());
// three zeros
if(numOfZeros > 2)
addResult(0,0,0);
return output;
}
private void addResult(int a, int b, int c){
int array[] = {a,b,c};
Arrays.sort(array);
List<Integer> result = new ArrayList<Integer>();
result.add(array[0]);
result.add(array[1]);
result.add(array[2]);
if(!visited.contains(result)){
visited.add(result);
output.add(result);
}
}
}
