Posted on 2013-05-01 23:13
小明 阅读(1913)
评论(0) 编辑 收藏 所属分类:
数据结构和算法
分析：
如果穷举所有这样的三元组，需要三重循环，算法的复杂度肯定是O(n
3)。
能不能把算法复杂度降到O(n
2)呢？答案是可以的。
首先我们要把数组排序(O(nlgn)),然后固定a,在剩余的数组中看能不能找到a+b+c=0
因为数组是排序的，我们把b指向第一个元素，c指向末尾。
三种情况：
a＋b＋c＝0：找到一组解
a＋b＋c<0: b向后移一位，增大和
a＋b＋c>0: c向前移一位，减小和
还要注意的是去掉重复的解，保证a和b都和上次的不同即可。
代码如下：
public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(
int[] num) {
ArrayList<ArrayList<Integer>> result =
new ArrayList<ArrayList<Integer>>();
if(num!=
null && num.length>=3){
Arrays.sort(num);
int len = num.length;
int lasta=0;
for(
int i=0;i<len-2;++i){
int a = num[i];
if(i>0 && a==lasta){
continue;
}
lasta = a;
int s = i+1;
int p = len-1;
int lastb = 0, j=0;
while(s<p){
int b = num[s];
int c = num[p];
int t = a+b+c;
if(t==0){
++s;
--p;
if(j>0 && b==lastb){
continue;
}
++j;
lastb = b;
ArrayList<Integer> tripplet =
new ArrayList<Integer>();
tripplet.add(a);
tripplet.add(b);
tripplet.add(c);
result.add(tripplet);
}
else if(t>0){
--p;
}
else{
++s;
}
}
}
}
return result;
}
}