15.三数之和

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

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

1.一刷

1. 先对数组进行排序，然后使用双指针法，这点非常难想到。因为只有数组有序才能使用双指针法，而双指针法是固定遍历子数组左端点nums[i]，low=i，high=nums.length-1,通过移动low和high来使三数之和逼近零。只有当low和high相碰时才退出这一轮循环。
2. 另一个难点在于去重。需要注意的是如果只去重不剪枝很可能会超时，因此把结果加入数组后，再通过while(nums[low]==nums[low-1])剪枝，这样子就不会超时了。
3. new ArrayList<>(Arrays.asList(a,b,c)):通过反射将数组转换成集合 Arrays.sort(nums):排序

public List<List<Integer>> threeSum(int[] nums) {
          Arrays.sort(nums);
          List<List<Integer>> res=new ArrayList<>();          
          for(int i=0;i<nums.length-2;i++)
           {
               if(nums[i]>0)
               return res;
               if(i>0&&nums[i]==nums[i-1])
               continue;
               int low=i+1,high=nums.length-1;
               while(low<high)
               {
                while(low<high&&nums[i]+nums[low]+nums[high]<0)
                low++;
                while(low<high&&nums[i]+nums[low]+nums[high]>0)
                high--;
                if(low<high&&nums[i]+nums[low]+nums[high]==0)
                {
               res.add(new ArrayList<>(Arrays.asList(nums[i],nums[low],nums[high])));
                    while (low<high && nums[high] == nums[high- 1]) high--;
                    while (low<high && nums[low] == nums[low+1]) low++;
                    high--;
                    low++;
                }
               }
           } 
           return res;}

2.二刷

第一遍先排序。接着固定中间位置元素，左右指针扩散移动。当前三数之和小于0则右指针向右移动，大于0则左指针向左移动。

此处去重的时机放在左右指针到达边界后，当前也可以放在统计结果后进行。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res=new HashSet<>();
       Arrays.sort(nums);
       for(int i=1;i<nums.length-1;i++){
           int mid=nums[i];
            int left=i-1,right=i+1;
            while(left>=0&&right<nums.length){
                //移动右指针
                if(nums[left]+mid+nums[right]<0){
                    while(right<nums.length&&nums[left]+mid+nums[right]<0) right++;
                    //找到右边界后去重
                    while(right+1<nums.length&&nums[right]==nums[right+1])right++;
                }
                else if(nums[left]+mid+nums[right]>0){
                    while(left>=0&&nums[left]+mid+nums[right]>0) left--;
                    //找到左边界后去重
                    while(left-1>=0&&nums[left]==nums[left-1])left--;
                }
                else{
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[left],mid,nums[right])));
                    left--;
                    right++;
                }
            }
       }
       return new ArrayList<>(res);
    }
}