NK5_给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

• 题目描述
  给出一个有n个元素的数组S&＃xff0c;S中是否有元素a,b,c满足a&＃43;b&＃43;c&＃61;0&＃xff1f;找出数组S中所有满足条件的三元组。

• 注意&＃xff1a;
  三元组&＃xff08;a、b、c&＃xff09;中的元素必须按非降序排列。&＃xff08;即a≤b≤c&＃xff09;
  解集中不能包含重复的三元组。

• 例如&＃xff0c;给定的数组 S &＃61; {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20)

• 我的解答
  最low的思想&＃xff0c;必超时&＃xff08;脑子啊脑子啊&＃xff09;

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {public ArrayList<ArrayList<Integer>> threeSum(int[] num){ArrayList<ArrayList<Integer>> list &＃61; new ArrayList<>();ArrayList<Integer> list_small &＃61; new ArrayList<>();Arrays.sort(num);for(int i &＃61; 0;i<num.length;i&＃43;&＃43;){for(int j &＃61; i &＃43; 1;j<num.length;j&＃43;&＃43;){for(int k &＃61; j &＃43; 1;k<num.length;k&＃43;&＃43;){if(num[i] &＃43; num[j] &＃43; num[k] &＃61;&＃61; 0){list_small.add(num[i]);list_small.add(num[i]);list_small.add(num[i]);list.add(list_small);list_small.clear();}}}}return list;}
}


• 通过解答
  思想&＃xff1a;先排序&＃xff0c;然后外层循环 固定开始元素1 &＃xff0c;设置 两个指针&＃xff0c;一个指针start指向元素2&＃xff08;元素2初始为元素1的下一个&＃xff09;&＃xff0c;一个指针end指向元素3&＃xff08;元素3初始为最后一个&＃xff09;
  内层循环&＃xff08;能找到3个元素条件start

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {public ArrayList<ArrayList<Integer>> threeSum(int[] num){//结果集合ArrayList<ArrayList<Integer>> list &＃61; new ArrayList<>();//排序Arrays.sort(num);//从 第一个元素到 倒数第二个元素&＃xff0c;外层循环配合内层循环 判断 含当前元素的每种情况&＃xff0c;内层循环筛选符合条件的for(int i &＃61; 0;i<num.length - 2;i&＃43;&＃43;){// 当前元素的下一个元素int start &＃61; i &＃43; 1;//最后一个元素int end &＃61; num.length - 1;//还够3个元素while(start < end){//此轮的三个元素和int sum &＃61; num[i] &＃43; num[start] &＃43; num[end];//因为已经排好序&＃xff0c;需要向移动下标向0靠近//需要中间指针更大的值if(sum < 0){start&＃43;&＃43;;}//需要末尾指针更小的值else if(sum > 0){end--;}//等于 0 的情况&＃xff0c;添加小集合到 大集合中else{ArrayList<Integer> list_small &＃61; new ArrayList<>();list_small.add(num[i]);list_small.add(num[start]);list_small.add(num[end]);if(!list.contains(list_small)){list.add(list_small);}//继续判断 是否还有含 num[i] 的不同组合start&＃43;&＃43;;end--;}}}return list;}
}