16 最接近的三数之和

本文最后更新于：2021年1月18日 晚上

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

示例：

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

提示：

  • 3 <= nums.length <= 10^3
  • -10^3 <= nums[i] <= 10^3
  • -10^4 <= target <= 10^4

Solution

  • 双指针
  • 利用 lambda 函数更新 sum。（参考LeetCode官方）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// @lc code=start
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        int best = 1e7;
        sort(nums.begin(), nums.end());
        
        // 根据差值的绝对值更新答案
        auto update = [&](int cur){
            if(abs(cur-target) < abs(best-target)){
                best = cur;
            }
        };

        for(int i=0; i<n; ++i){
            if(i>0 && nums[i]==nums[i-1]) continue;
            int l=i+1, r=n-1;
            while(l<r){
                int sum = nums[i]+nums[l]+nums[r];
                if(sum==target) return target;
                update(sum);
                if(sum<target){
                    int low = nums[l];
                    while(l<r && nums[l]==low)
                        l+=1;
                }
                else{
                    int high = nums[r];
                    while(l<r && nums[r]==high)
                        r-=1;
                }
            }
        }
        return best;
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！