先对数组进行排序,再使用双指针 ,代码如下
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
int len = num.length;
if(len<3){
return res;
}
Arrays.sort(num);
for (int i = 0; i < len-2; i++) {
if (num[i]>0) break;
if (i>0&&num[i] == num[i-1]) continue;
int left = i+1;
int right = len-1;
while (left<right){
int sum = num[i] + num[left] + num[right];
if (sum>0){
while (left<right&&num[right] == num[--right]);
}else if (sum<0){
while (left<right &&num[left] == num[++left]);
}else {
ArrayList<Integer> list = new ArrayList<>();
list.add(num[i]);
list.add(num[left]);
list.add(num[right]);
res.add(list);
while (left<right&&num[right] == num[--right]);
while (left<right &&num[left] == num[++left]);
}
}
}
return res;
}
}