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

题目分析

1. 题目给出一个数组nums和一个目标值target
2. 题目要求我们在nums数组中任意选择三个数字，使其之和与目标值之差的绝对值最小
3. 返回满足第2点要求的三数之和

方法一：暴力法

• 实现思路
  • 三重循环任意选择数组中的三个数字
  • 对选出来的三个数字进行加和，并与目标值作差求绝对值
  • 每次比较新的绝对值是否更加接近于目标值，并根据判断结果更新最终的三数之和

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int ClosestSum(vector<int>& nums, int target) {
        // write code here
        int n = nums.size();
        int mn = 10001;
        int res;
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                for(int k = j+1; k < n; k++) {        // 三重循环挑选三个数字
                    int a = nums[i];
                    int b = nums[j];
                    int c = nums[k];
                    int sum = a +b + c;
                    int x = abs(sum - target);
                    if(x < mn) {                      // 比较本次是否三个数字和接近目标数，并更新最终结果
                        mn = x;
                        res = sum;
                    }
                    
                }
            }
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：$O(n^3)O(n^3)$，其中$nn$是$numsnums$数组的长度，由于存在三重循环，所以时间代价是$nn$的立方关系
• 空间复杂度：$O(1)O(1)$，引入了常数级别的空间代价

方法二：排序+双指针

• 实现思路
  • 首先对nums数组进行排序
  • 然后外层循环遍历nums数组，确定三数中第一个数字的位置。
  • 内层循环中控制双指针，左指针指向第一个确定位置数字的下一个数字，右指针指向nums数组的最右侧的位置，这样左右指针分别指向了第一个数字右侧的数字中最小和最大的两个数字
  • 如果当前三个指向的数字之和与目标值的差距更小，则更新当前的目标结果(三数之和)和当前的差距
  • 如果当前三个指向的数字之和大于目标值，则将右指针左移，减小三数之和，进行下一轮的与目标值比较
  • 如果当前三个指向的数字之和小于目标值，则将左指针右移，增大三数之和，进行下一轮的与目标值比较
  • 最终返回最接近目标值的三数之和即可

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int ClosestSum(vector<int>& nums, int target) {
        // write code here
        int n = nums.size();
        int minDiff = 10001, ans, temp;
        sort(nums.begin(), nums.end());                // 排序
        for(int i = 0; i < n; i++){
            for(int j = i + 1, k = n - 1; j < k;){     // 首尾选择两个数字
                temp = nums[i] + nums[j] + nums[k];    // 计算暂时的三数之和
                if(abs(temp - target) < minDiff){      // 如果三数和与目标数之差变小则更新结果
                    minDiff = abs(temp - target);
                    ans = temp;
                }
                if(temp > target) k--;                 // 如果三数和偏大，则k位置指针左移将三数和变小
                else if(temp < target) j++;            // 如果三数和偏小，则j位置指针右移将三数和变大
                else return ans;
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，其中$nn$表示$numsnums$数组的长度，其中排序的时间代价为$O(nlogn)O(nlogn)$，而排序后仍旧存在双重循环的时间代价为$O(n^2)O(n^2)$，后者对整体时间开销起决定性因素。
• 空间复杂度：$O(1)O(1)$，只引入了常数级别的空间代价。