题目链接:
三数之和

1.题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

2.题解

2.1.三层for循环

一开始就知道三层for循环不是最优解，想着先写一个答案出来，再去优化，可是写三层for循环的过程中，去重一直有问题，所以放弃了。搜了别人的答案，三层for循环性能很差，就不考虑了。

2.2.排序

在尝试使用三层for循环进行解答的时候，去重，发现如果可以先排个序，就可以解决相同数过滤的问题。
首先为什么要排序？
三数之和为0，排除[0,0,0]这种特殊情况，肯定有一个是负数，这样排序之后，我们选取负数作为我们的基数，然后寻找b和c，使得b+c=0-a,这样就将三数之和转化为了两数之和，复杂度会降低。
下面是详细步骤
首先给数组排序

      //定义返回对象
      List<List<Integer>> list = new ArrayList<>();
        //先排序
     Arrays.sort(nums);

然后我们开始遍历，范围是0~nums.length-1
我们要以负数为基准，所以当遍历到的数大于0的时候退出循环

 for (int i = 0; i < nums.length; i++) {
      //如果nums[i]>0的话，代表后面的都大于0，3sum不会小于0
      if (nums[i] >0) {
            break;
      }
}

将外层循环的范围定在负数里，当遇到重复的负数的时候，continue即可,这样可以过滤掉大部分重复的负数

 for (int i = 0; i < nums.length; i++) {
      //如果nums[i]>0的话，代表后面的都大于0，3sum不会小于0
      if (nums[i] >0) {
            break;
      }
      //这是在数组的负数部分
      //如果连续2个数相等，就继续下一循环
      //这里判断nums[i]和nums[i-1]是否相等，而不是nums[i]和nums[i+1]，
      //是因为这样如果nums[i]和nums[i-1]相等，那么nums[i]和nums[i-1]还是会参与
循环
     //而nums[i]和nums[i+1]相等，会导致nums[i]被跳过，导致结果不全
      if(i>0&&nums[i]==nums[i-1]){
           continue;
      }
}

下面定义下一个循环的变量

 for (int i = 0; i < nums.length; i++) {
      //如果nums[i]>0的话，代表后面的都大于0，3sum不会小于0
      if (nums[i] >0) {
            break;
      }
      //这是在数组的负数部分
      //如果连续2个数相等，就继续下一循环
      //这里判断nums[i]和nums[i-1]是否相等，而不是nums[i]和nums[i+1]，
      //是因为这样如果nums[i]和nums[i-1]相等，那么nums[i]和nums[i-1]还是会参与
循环
     //而nums[i]和nums[i+1]相等，会导致nums[i]被跳过，导致结果不全
      if(i>0&&nums[i]==nums[i-1]){
           continue;
      }
      //类似于双指针，一个指针从左向右移动，一个指针从右向左移动
      int j = i + 1;
      int k = nums.length - 1;
}

下面这一步是寻找符合条件的结果的过程,先给出完整的代码，再把while循环单独拿出来看

 for (int i = 0; i < nums.length; i++) {
      //如果nums[i]>0的话，代表后面的都大于0，3sum不会小于0
      if (nums[i] >0) {
            break;
      }
      //这是在数组的负数部分
      //如果连续2个数相等，就继续下一循环
      //这里判断nums[i]和nums[i-1]是否相等，而不是nums[i]和nums[i+1]，
      //是因为这样如果nums[i]和nums[i-1]相等，那么nums[i]和nums[i-1]还是会参与
循环
     //而nums[i]和nums[i+1]相等，会导致nums[i]被跳过，导致结果不全
      if(i>0&&nums[i]==nums[i-1]){
           continue;
      }
      //类似于双指针，一个指针从左向右移动，一个指针从右向左移动
      int j = i + 1;
      int k = nums.length - 1;

      while (j<k) {
          if (k<nums.length-1&&nums[k]==nums[k+1]||nums[i] + nums[j] + nums[k] > 0) {
               k--;
          } else if (j>i+1&&nums[j]==nums[j-1]||nums[i] + nums[j] + nums[k] < 0) {
               j++;
          } else {
               List<Integer> ints = new ArrayList<>();
               ints.add(nums[i]);
               ints.add(nums[j++]);
               ints.add(nums[k--]);
               list.add(ints);
          }
       }
}

把while单独拿出来

 while (j<k) {
     if (k<nums.length-1&&nums[k]==nums[k+1]||nums[i] + nums[j] + nums[k] > 0) {
            k--;
     } else if (j>i+1&&nums[j]==nums[j-1]||nums[i] + nums[j] + nums[k] < 0) {
            j++;
     } else {
            List<Integer> ints = new ArrayList<>();
            ints.add(nums[i]);
            ints.add(nums[j++]);
            ints.add(nums[k--]);
            list.add(ints);
      }
  }

首先，while成立的条件是j<k，即左指针的值要小于又指针的值，当j>=k的时候结束循环。
第一个判断，if是判断右指针的，
第一个条件:

k<nums.length-1

第一次循环k=nums.length-1,k+1会超出数组长度限制，所以现在k<nums.length-1

第二个条件:

nums[k]==nums[k+1]

当我们遍历右指针的时候，如果相邻2个数相等，就执行k--,右指针继续继续向左移动。

第三个条件:

nums[i] + nums[j] + nums[k] > 0

三数之和大于0，说明nums[k]的值比较大，因为数组是从左到右升序的，所以这种情况下也执行k--,右指针继续向左移。

第二个判断,else if是用来判断左指针的，
第一个条件:

j>i+1

这个判读条件很重要，是点睛之笔。
由于这个while循环是我看的别人的答案，一开始我也想不通，为啥这个条件很重要，后来我把这个条件注释掉，然后报错了，我就打断点跟进去看，下面拿报错的例子来说明一下
给定如下数组

public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        List<List<Integer>> list = threeSum(nums);
        System.out.println(list);
    }

我们把j>i+1这个条件注释掉，看看运行结果如何

//注释掉j>i+1的运行结果
[[-1, 0, 1]]

然后把注释放开

//不注释j>i+1的结果
[[-1, -1, 2], [-1, 0, 1]]

如果我们不写代码，单纯的穷举结果，第二种的结果是正确的。
为什么会有这种现象呢？
看一下main函数中的数组，数组经过排序是这样

[-4, -1, -1, 0, 1, 2]

当i=1,j=2的时候，num[i]=-1,nums[j]=-1,j=i+1,如果没有j>i+1这个判断条件的话，
nums[j]==nums[j-1]这个条件为true,就会执行j++,然后执行下一次循环，而此时nums[i] + nums[j] + nums[k] < 0，这种情况就被漏掉了，这个条件的厉害之处在于，照顾到了遍历左指针时，相邻2数相等这个情况，还不会造成答案重复。
继续看else if的第二个判断条件:

nums[j]==nums[j-1]

这个条件保证了如果在遍历左指针的时候，如果相邻2数相等，就执行j--，进入下一次循环，和上一个条件j>i+1保证了不会漏答案。

第三条件:

nums[i] + nums[j] + nums[k] < 0

三数之和小于0，说明nums[j]的值比较小，左指针向右移，执行j++，进入下一次循环。
现在排除掉所有不符合的情况，剩下的都是三数之和等于0的情况了。添加到list中作为最后返回的结果。

2.3.完整代码

   public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        //先排序
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            //如果nums[i]>0的话，代表后面的都大于0，3sum不会小于0
            if (nums[i] >0) {
                break;
            }
            //如果连续2个数相等，就继续下一循环
            //这是在数组的负数部分
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;

            while (j<k) {
                if (k<nums.length-1&&nums[k]==nums[k+1]||nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                } else if (j>i+1&&nums[j]==nums[j-1]||nums[i] + nums[j] + nums[k] < 0) {
                    j++;
                } else {
                    List<Integer> ints = new ArrayList<>();
                    ints.add(nums[i]);
                    ints.add(nums[j++]);
                    ints.add(nums[k--]);
                    list.add(ints);
                }
            }
        }
        return list;
    }

3.一点说明

一开始自己做的时候，使用的java，想用三层for循环暴力解答，可是去重一直有问题，前前后后折腾了一周也没做出正确的答案。后面放弃了。在做去重的时候，想到了先排序再过滤的思路，不过没有动手去做。
后来受不了了开始百度答案，看到了这篇文章:
三数之和
文章中做了三层for循环和排序后再处理的耗时对比。这篇文章的思路是先排序，然后以负数为基准，去找另外2个数，将问题降级成2数之和。应该说这种是最好的解答方案，如果有更好的思路，也可以评论区讨论。
我基于java，再排序后，去重还是有问题，所以去leetcode上找了一下题解，前一页的题解基本上不符合我的要求，所以往后翻，在第二页找到了满意的答案
while循环那一块就是这个答案的作者提供的,链接在下方贴出:
我认为的最好的java题解
j>i+1这个判断条件真的用的太妙了。
这道题我没有完整的做出来，是看了答案之后在debug调试理解的过程的。如果有自己理解不了的地方，建议可以Debug调一调，看一下具体的过程，在遍历的过程中到底做了些什么。