三数之和（双指针）

算法原理

暴力解法：

排序+暴力枚举+set去重

双指针

这道题的大体框架就是固定一个数，使三个数的和转换成另两个数的和。
我们通过示例一可以发现如果一个一个枚举的话有三种情况，但是看答案发现它又筛选掉了一种情况，因此需要进行去重。
主要的难点其实就是去重了。当然还有很多小细节不能忽略。

• 1，先进行排序
• 2，去重
  • 找到一种结果之后，left和right指针要跳过重复元素
  • 当使用完一次双指针算法之后，i也要跳过重复元素
• 3，不漏
  • 找到一种结果之后，不要停，缩小区间，继续寻找。

代码实现

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0;i< nums.length-2;){
            //这是一处优化的小细节
            if(nums[i] >0){
                break;
            }
            int target = -nums[i];
            int left = i+1;
            int right = nums.length-1;
            int n = nums.length;
            while(left < right ){
                if(nums[left] +nums[right] > target ){
                    right--;
                }else if(nums[left] +nums[right] < target){
                    left++;
                }else{
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left], nums[right])));
                    left++;
                    right--;
                    //去重操作
                    while(left<right && nums[right] == nums[right +1]){
                    right--;
                }
                    while(left < right && nums[left] == nums[left -1]){
                    left++;
            }
        }
    }
    i++;
    //别忘了i也要去重
        while(i<n && nums[i] == nums[i -1]){
            i++;
        }
}
        return list;
    }
}

以上排完序再去重的方法很新颖，要好好体会。