算法007——三数之和

力扣——三数之和（点击跳转）

做这道三数之和的题之前一定要先看我的上一篇笔记——两数之和（点击跳转），只有把这个弄清楚这个三数之和才能明白

因为要去重，我们可以先将数组排序

我们先固定一个数，在剩下的数中找到两个数的和是这个被固定数的相反数，还是利用双指针的思想。

在这里插入图片描述
注意：固定的数一定要是小于等于0的数，如果是正数，如下图所示，此时 i 为 1，那么 target = -1，后面都为正数，根本找到不到和为负数的两个数

根据前两篇博客我们可以完成查找，原理相同，不做过多讲解，可以翻看前两篇博客

在指针移动的时候，我们会遇到找到结果的时候，如下图所示，此时不要停，要缩小区间，继续寻找
在这里插入图片描述

最后我们要思考的是如何去重，我们已经将数组排序

在指针移动过程中，会遇到相同的元素，如下图所示，将元素跳过即可
在这里插入图片描述

当第一个固定的元素找完之后，i 会遍历整个数组， i 也会遇到相同的元素，也需要跳过
在这里插入图片描述

在去重的时候要注意 越界访问

代码如下

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length - 1;
        for(int i = 0;i <= n;){//固定 i
            if(nums[i] > 0) break;
            int left = i + 1;//left 是从 i 的后一个开始的
            int right = n;
            int target = -nums[i];
            while(left < right){
                 int sum = nums[left] + nums[right];
                 if(sum > target){
                    right--;
                 }else if(sum < target){
                    left--;
                 }else{
                    //找到两个数存放到 ret 当中
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    //不停，缩小范围，继续寻找
                    left++;
                    right--;
                    //去重同时避免越界
                    while(left < right && nums[left] == nums[left - 1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]){
                        right--;
                    }
                 }
                 //对 i 进行去重，也要注意避免越界
                 i++;//在这里进行 i++ 的操作，for循环语句的要记得删除
                 while(i <= nums.length && nums[i] == nums[i--]){
                    i++;
                 }
            }
        }
        return ret;
    }
}