LeetCode 16. 最接近的三数之和

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题解

• 类似于三数之和，先对数组进行排序。
• 取第 i 个数，设定 j = i+1 为下一个数，k = size-1 为最右边的数
• 计算三数之和 sum = nums[i] + nums[j] + nums[k]，得出差值 abs(sum - target)，如果为最小差值小则记录 sum 和最小差值。
• 比较 sum 与目标大小
  1. sum 比 target 大，则 --k。
  2. sum 比 target 小，则 ++j。
  3. sum 等于 target ，则最接近 target 。

// C++
int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int size = (int)nums.size();
    int minOffset = INT_MAX;
    int sum = 0;
    for (auto i = 0; i < size - 2; ++i) {
        int n1 = nums[i];
        int j = i + 1;
        int k = size - 1;
        while (j < k) {
            int n2 = nums[j];
            int n3 = nums[k];
            int newSum = n1 + n2 + n3;
            int offset = abs(newSum - target);
            if (offset < minOffset) {
                minOffset = offset;
                sum = newSum;
            }
            if (newSum > target) {
                --k;
            } else if (newSum < target) {
                ++j;
            } else {
                return target;
            }
        }
    }
    return sum;
}