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

题意整理

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

方法一（暴力循环）

1.解题思路

直接三层循环，遍历所有可能的第1个数、第2个数、第3个数，每次选择绝对值尽可能小的，并更新对应的三数之和。

2.代码实现

import java.util.*;


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

3.复杂度分析

• 时间复杂度：总共三层循环，需要执行$n\ast (n-1)\ast (n-2)\mathrm{/}6n*(n-1)*(n-2)/6$次，所以时间复杂度是$O(n^3)O(n^3)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。

方法二（排序+双指针）

1.解题思路

• 首先对数组进行排序，方便双指针进行查找。
• 然后遍历nums数组确定第1个数，并在剩下的数中，通过双指针确定第2个数和第3个数。
• 其中，l下标对应第2个数，r下标对应第3个数。如果存在更小的绝对值，则更新三数之和sum。将sum尽可能地逼近target，如果小于target，则寻找更大的sum，l指针右移，如果大于target，则寻找更小的sum，r指针左移，如果等于target，则绝对值已经最小，返回sum。

图解展示：

2.代码实现

import java.util.*;


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

3.复杂度分析

• 时间复杂度：排序的时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$，此外两层循环，最多需要执行$(n-1)\ast (n-2)\mathrm{/}2(n-1)*(n-2)/2$次，所以时间复杂度是$O(n^2)O(n^2)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。