数组中相加为0的三元组
数组中相加和为0的三元组
https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=117&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
if (num==null) return list;
Arrays.sort(num);
for (int i=0;i<num.length-2;i++){
//固定第一个元素 去重
if(i>0 && num[i]==num[i-1]) continue;
ArrayList<ArrayList<Integer>> res = getList(i,num);
list.addAll(res);
}
return list;
}
//转化为有序数组中找两个数等于目标数
private ArrayList<ArrayList<Integer>> getList(int i, int[] num) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
int target = 0-num[i];
int left = i+1;
int right = num.length-1;
while (left<right){
if (num[left]+num[right]>target){
right--;
}else if(num[left]+num[right]==target){
//去重
if(left>i+1 && num[left]==num[left-1]) {
left++;
continue;
}
ArrayList<Integer> list = new ArrayList<>();
list.add(num[i]);
list.add(num[left]);
list.add(num[right]);
res.add(list);
left++;
}else {
left++;
}
}
return res;
}