Posted on 2013-05-01 23:13
小明 閱讀(1929)
評論(0) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
分析：
如果窮舉所有這樣的三元組，需要三重循環(huán)，算法的復(fù)雜度肯定是O(n
3)。
能不能把算法復(fù)雜度降到O(n
2)呢？答案是可以的。
首先我們要把數(shù)組排序(O(nlgn)),然后固定a,在剩余的數(shù)組中看能不能找到a+b+c=0
因?yàn)閿?shù)組是排序的，我們把b指向第一個元素，c指向末尾。
三種情況：
a＋b＋c＝0：找到一組解
a＋b＋c<0: b向后移一位，增大和
a＋b＋c>0: c向前移一位，減小和
還要注意的是去掉重復(fù)的解，保證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;
}
}