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

题目的主要信息：

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

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

方法一：

暴力法。用min保存已知最小的差绝对值，枚举所有可能的三个数组合，计算当前三数之和与目标数之间的差的绝对值，然后和min比较，在min中记录较小的值，同时sum记录已知最接近的三数之和，枚举结束后，返回sum。

具体做法：

class Solution {
public:
    int ClosestSum(vector<int>& nums, int target) {
        int n=nums.size();
        int min=9999;
        int sum=0;//保存三数之和
        //遍历所有可能的三个数
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    //temp记录当前三数之和与目标数之差绝对值
                    int temp=abs(nums[i]+nums[j]+nums[k]-target);
                    if(temp<min){//min中保存已知最小的差绝对值
                        min=temp;
                        sum=nums[i]+nums[j]+nums[k];//sum保存已知最小的三数之和
                    }
                }
            }
        }
        return sum;
    }
};

复杂度分析：

• 时间复杂度：$O(n^3)O(n^3)$，三重for循环。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

首先对数组进行排序，依旧遍历所有可能的三数，但是我们用双指针进行优化，避免不必要的遍历。遍历所有可能的第一位数，l指针从数组最小开始遍历，为第二位数，r指针从数组末尾开始遍历，为第三位数，计算i、l、r三数之和sum，在res中保存差值最小的三数之和，然后根据sum的大小调整指针移动，l向右移动，三数之和变大，r向左移动，三数之和变小，根据l、r的调整使得差值越来越小。最后返回res。

具体做法：

class Solution {
public:
    int ClosestSum(vector<int>& nums, int target) {
        int n=nums.size();
        sort(nums.begin(),nums.end());//对数组进行排序
        int res=nums[0]+nums[1]+nums[2];//初始化
        for(int i=0;i<n;i++){//遍历所有可能的第一位数
            int l=i+1,r=n-1;//l为第二位数，r为第三位数
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(abs(sum-target)<abs(res-target)){//res中保存差值最小的三数之和
                    res=sum;
                }
                //根据sum的大小调整指针
                if(sum<target){//l向右移动，三数之和变大
                    l++;
                }else if(sum>target){//r向左移动，三数之和变小
                    r--;
                }else if(sum==target){
                    return sum;
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，for循环嵌套while循环。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。