题目描述：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
题目难度：中等
分析：
比较经典的一道题。题目要求在一个数组中找到3个数，使得三数相加等于0，并且这三数一体不重复。比较好抽象为排列组合问题，找出所有的3数组合，去除重复，然后判断相加是否等于0，或者先判断是否等于0，把所有等于0的组合放在一起再去除重复，但是问题难就难在，怎么去重这个步骤。
较简单的方法就是通过Set集合去重，但是要注意[1, 2, 3] 和 [1, 3, 2] 并不算重复，必须连顺序也一样才算重复。这里可以对数组排序，然后按照顺序去执行逻辑，那么就不需要考虑重复了。
排序后的思路：首先从下标0开始，选取一个基准，然后对右边的数组进行操作，分别用两个指针一前一后，这样再加上一个基准，就是3个指针，判断这三个数相加是否等于0，是的话就放入Set中，要按顺序放，[基准，左指针，右指针] 这样就可以达到去重的目的。
代码如下：
class Solution { public List<List<Integer>> threeSum(int[] nums) { // 定义一个Set集合用来存放结果集，去重 Set<List<Integer>> set = new HashSet(); // 用来判断基准是否重复，很明显如果基准重复了，那么即使相加等于0，也是重复的数据 Set<Integer> set1 = new HashSet(); // 如果数组为空，直接返回一个空集合 if(nums.length == 0) return new ArrayList<>(set); // 对数组进行排序，简化去重操作 Arrays.sort(nums); // 因为基准数只和右边的数进行逻辑处理，所以循环到倒数第三个就可以了 for(int i = 0; i < nums.length-2; i++){ // 每个基准判断一次即可（测试用例里有个很恶心的数组，全部都是0，不判断的话会超时） if(!set1.add(nums[i])) continue; // 左指针从i的下一位开始 int j = i + 1; // 右指针从数组最后一位开始 int k = nums.length - 1; // 判断循环结束的条件就是左 < 右 while(j < k){ // 三数相加的临时变量 int sum = nums[i] + nums[j] + nums[k]; /* * 算法核心：如果sum > 0，那么说明这三个数偏大，而基准是不能动的， * 就左右指针来看，左指针右移数值会更大，右指针左移数值才会变小， * 通过不断的移动指针就可以最终找到我们想要的结果， * 这题和前面一道 盛水最多的容器 道理一样 */ if(sum > 0){ k--; }else if(sum < 0){ j++; }else{ // 如果正好等于0，那么把数值加入Set集合，并同时移动左右指针 set.add(Arrays.asList(nums[i], nums[j++], nums[k--])); } } } return new ArrayList<>(set); } }
总结：
时间复杂度为O ( n 2 ) ，需要双层循环，效率一般，但是毕竟好理解，代码量也不多，就应该先从解决问题着手，然后再考虑优化，先不管三七二十一，通过所有测试用例，排名靠前的代码，一般都没有注释，思路比较奇特。（毕竟是大佬，想法比较难琢磨）。再一次用到了双指针算法，可见这个套路能解决很多问题。
