题解 | #最接近的三数之和#

题目主要信息

给定一个数组 nums 和一个目标值 target ，请问从 nums 中选出三个数，使其之和尽量接近目标数，即三数之和与目标数只差绝对值尽可能小。

返回满足题面要求的三数之和。

方法一：直接暴力

具体方法

三层循环求解三个和最小的值

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int ClosestSum (int[] nums, int target) {
        // write code here
        int len = nums.length;
        // 保存最小的数
        int min=Integer.MAX_VALUE;
        //记录结果
        int result = 0;
        //三层循环，遍历第1个数、第2个数和第3个数
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                for(int k=j+1;k<len;k++){
                    //如果绝对值小于min，则更新min
                    if(Math.abs(nums[i]+nums[j]+nums[k]-target)<min){
                        min=Math.abs(nums[i]+nums[j]+nums[k]-target);
                        //同时跟新result
                        result = nums[i]+nums[j]+nums[k];
                    }
                }
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}{n}^3\mathrm{）}O（n^3）$三层for循环
• 空间复杂度：$O\mathrm{（}1\mathrm{）}O（1）$一个临时变量

方法二：排序+双指针

具体方法

借助双指针，可以对枚举的过程进行优化。用 pb 和 pc分别表示指向 b和 c的指针，初始时，pb指向位置 i+1，即左边界；pc指向位置 n−1，即右边界。在每一步枚举的过程中，我们用 $a+b+ca+b+c$来更新答案，并且：

• $a+b+c\ge targeta+b+c\ge target$，那么就将 pc向左移动一个位置；
• ，那么就将 pb向右移动一个位置。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int ClosestSum (int[] nums, int target) {
        // write code here
        int len = nums.length;
        //排序
        Arrays.sort(nums);
        //记录结果
        int result = nums[0]+nums[1]+nums[2];
        for(int i=0;i<len;i++){
            //通过双指针确认第2个数和第3个数
            int left = i+1,right = len-1;
            while(left < right){
                //i下标对应第1个数，l下标对应第2个数，r下标对应第3个数
                int sum=nums[i]+nums[left]+nums[right];
                //如果有更小的绝对值，则跟新sun
                if(Math.abs(sum-target)<Math.abs(result-target)){
                    result = sum;
                }
                //如果sum小于target，则朝sum变大的方向移动
                if(sum<target){
                    left++;
                }
                //如果sum大于target，则朝sum变小的方向移动
                else if(sum>target){
                    right--;
                }
                //如果等于，则绝对值为0，直接返回sum
                else{
                    return sum;
                }
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}{n}^2\mathrm{）}O（n^2）$，for循环中嵌套了while循环
• 空间复杂度：$O\mathrm{（}1\mathrm{）}O（1）$存结果的临时变量