Leetcode15. 三数之和(×)

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

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

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

三重for循环，超时典范：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
         Set s = new HashSet();
         for(int i = 0;i<nums.length; i++){
             for(int j = i+1; j<nums.length; j++){
                 for(int k = j+1; k<nums.length; k++){
                     if(nums[i]+nums[j]+nums[k]==0){
                          ArrayList<Integer> list = new ArrayList();
                             list.add(nums[i]);
                             list.add(nums[j]);
                             list.add(nums[k]);
                             Collections.sort(list);
                             s.add(list);
                     }
                 }
             }
         }
         return new ArrayList<>(s);
    }
}

【题解】：
题解都是直接丢双指针的解题思路，没有讲如何从暴力解逐渐推到双指针解法的（大佬的常规思路都是我难以企及的灵光一现），下面讲一下我的理解： 首先，如果用暴力解，用一个三重循环遍历那么时间复杂度在O()，然后稍微进行优化，根据题目：找到三元组不能重复

可以想到，如果要排序（能保证重复出现的数字在一起，并且时间复杂度为O(NlogN)，没啥影响）
可以在第二重循环的枚举中找到不小于当前第一重循环的枚举元素
和第三重循环同理，找到不小于第二重循环的枚举元素
=> 那么能想到了排序，但是本质上还是三重循环，那么时间复杂度还是O()，继续优化，将下面的两重循环变成一重循环：

可以发现我们是固定了第一个数然后去找其他两个数的，那么可以将后面两个数看成一个数，那么问题就变成了在有序数组中从[i+1, len-1]这个范围内找到一个符合要求的数，那么就变成了双指针问题，而这个数的值不再是mid，而是两个边界left和right的和。而指针的移动条件就是：如果当前的sum值太大，那么右指针就移动；如果sum太小，那么左指针就移动；如果值正好，那么就是当前值，并且左指针右移，右指针左移（因为是找到所有满足的解）；循环的结束条件就是左右指针相遇 而双指针情况下，第二三重循环就从O()变成O(N)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //在第一重循环中，判断当前数是否和前一个数一样，如果一样，就跳过本次循环
//而在双指针中，如果找到一组正确解后，需要将left和right分别右移/左移到和当前值不一样的地方
           Arrays.sort(nums);
           List<List<Integer>> res = new ArrayList<>();
           for(int i =0;i<nums.length-2;i++){
               int base = nums[i];
               if(base>0){//按顺序排序，base都大于0了后面应该没有了
                   return res;
               }
               //断当前数是否和前一个数一样，如果一样，就跳过本次循环
               if(i>0&&nums[i]==nums[i-1]){//
                   continue;
               }
               int left = i + 1;
               int right = nums.length - 1;
               while(left<right){
                   if(nums[i]+nums[left]+nums[right]==0){
                       List<Integer> list = new ArrayList<>();
                       list.add(nums[i]);
                       list.add(nums[left]);
                       list.add(nums[right]);
                       res.add(list);
                       //直到找到和下一次结果不一样的
                       while(left<right&&nums[left]==nums[left+1]){
                           left++;
                       }
                       while(left<right&&nums[right]==nums[right-1]){
                           right--;
                       }
                       left++;
                       right--;
                   }else if(nums[i]+nums[left]+nums[right]>0){
                       right--;
                   }else{
                       left++;
                   }
               }
           }
           return res;
    }
}