Leetcode算法练习：三数之和

这类题型是两数求和的变种题型，我们这两种题型对比来分析，总结它们的算法思路，举一反三加深印象

(1) 三数求和

题目跳转链接

AC代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);//先对数组中的元素进行排序
        List<List<Integer>>ans=new ArrayList<>();//存放结果

        int len=nums.length;
        for(int i=0;i<len-2;i++){
            if(nums[0]>0){//如果最小的元素都大于0则不存在三数之和等于0
                break;
            }
            if(i>0&&nums[i]==nums[i-1]){//去除重复的情形
                continue;
            }

            //从第i个元素的后一个元素开始遍历，采用双指针
            int left=i+1;
            int right=len-1;

            while(left<right){
                if(nums[left]+nums[right]+nums[i]>0){
                    right--;
                }else if(nums[left]+nums[right]+nums[i]<0){
                    left++;
                }else{//满足条件，将三元组保存到ans数组中
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[left]);
                    tmp.add(nums[right]);
                    ans.add(tmp);
                    left++;right--;
                    //去除重复的三元组
                    while(left<right&&nums[left]==nums[left-1]){
                        left++; 
                    }

                    while(left<right&&nums[right]==nums[right+1]){
                        right--;
                    }
                }
            }
        }
        return ans;
    }
}

(2) 两数求和

题目跳转链接

AC代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len=nums.length;
        int[] ans= new int[2];//存放结果
        boolean flag=false;//是否取得最终结果的标志位
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(nums[i]+nums[j]==target){//满足条件，将下标存放在ans数组中
                    ans[0]=i;
                    ans[1]=j;
                    flag=true;
                    break;
                }
            }
        }
        return ans;
    }
}

思路解读

对比点1：题目（1）的要求是在 $n u m s$ 数组中找到三个数构成一个三元组，约束条件是这三个数之和是为0；题目（2）要求是在 $n u m s$ 数组中找到两个数满足，约束条件是这两个数之和等于规定的一个数值，并且要取这两个数在 $n u m s$ 数组对应的下标
对比点2：基于对比点1，题目（1）通过两重循环逐一遍历当找到第一对满足条件的两个数，则停止遍历，将两个数在数组中对应的下标存储在 $a n s$ 数组中并将结果返回；题目（2）如果采用三重循环遍历，提交代码的时候会出现运行超时的现象，为了降低时间复杂度解决的办法就是 $n^3$ 降低到 $n^2$ 。我们的解决方案–双指针法，思路如图所示：

首先将 $n u m s$ 数组进行排序，满足条件的三元组中指向第一个元素的指针为 $i$ 第二个元素为 $l e f t$ , 第三个元素为 $r i g h t$ 。
在这里插入图片描述
先固定指针 $i$ 指向的元素，同时移动 $l e f t$ 和 $r i g h t$ 指针，当 $l e f t$ $r i g h t$ 指针相遇时则将 $i$ 指针移动一个单位;

遍历的过程中如果第一个元素的数值都是整数，我们直接中止遍历，得出结论不存在三个整数，使得这三个整数之和为0；
在双指针移动的过程中，如果 $n u m s [i] + n u m s [l e f t] + n u m s [r i g h t] > 0$ 时，我们需要将 $r i g h t$ 指针向左移动一个单位；如果 $n u m s [i] + n u m s [l e f t] + n u m s [r i g h t] < 0$ 时，我们需要将 $l e f t$ 指针向右移动一个单位；如果 $n u m s [i] + n u m s [l e f t] + n u m s [r i g h t] = 0$ 时，我们需要将 $r i g h t$ 指针向左移动一个单位，将 $l e f t$ 指针向右移动一个单位；（注意点1：这时我们需要检查是否产生重复的三元组的情况，如果有则需要跳过，不记录当前的结果；注意点2：在双指针相遇时，移动指针i，我们也需要检查如果i指针移动后指向的元素和之前相同则继续向后移动一个单位，这样可以避免记录重复的三元组）