leetcode16.最接近的三数之和

Posted on | In |
Words count in article: 303 | Reading time ≈ 1

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例：

1
2
3
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

分析：

1
2
1、枚举每个数，先确定nums[i]，在排序后的情况下，通过双指针l，r分别从左边l = i + 1和右边n - 1
往中间靠拢，找到nums[i] + nums[l] + nums[r] 接近target的所有符合条件的搭配

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        pair<int, int> res = {INT_MAX, INT_MAX};
        for (int i = 0;i < nums.size();i ++) {
            for (int j = i + 1, k = nums.size() - 1;j < k;j ++) {
                while (j < k - 1 &&  nums[k - 1] + nums[i] + nums[j] >= target) k --;
                int s = nums[k] + nums[i] + nums[j];
                res = min(make_pair(abs(s - target), s), res); // 大于target时
                if (k - 1 > j) { // 小于target时
                    s = nums[k - 1] + nums[i] + nums[j];
                    res = min(make_pair(abs(s - target), s), res);
                }
            }
        }

        return res.second;
    }
};

[原题链接](16. 最接近的三数之和 - 力扣（Leetcode）)

0%