算法 16. 最接近的三数之和

LeetCode https://leetcode.cn/problems/3sum-closest/

题目描述

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

思路

排序+双指针, 先将数组排序, 然后枚举第一个元素, 移动双指针, 找到最接近的数

代码

class Solution {
public:
    int threeSumClosest(std::vector<int>& nums, int target) {
        int size = (int)nums.size();
        if (size < 3)
            return 0;

        std::sort(nums.begin(), nums.end());

        int result = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < size - 2; ++i) {
            int left = i + 1;
            int righ = size - 1;
            while (left < righ) {
                int sum = nums[i] + nums[left] + nums[righ];
                if (sum == target)
                    return sum;
                if (abs(target - sum) < abs(target - result))
                    result = sum;
                if (sum > target)
                    --righ;
                else
                    ++left;
            }

        }
        return result;
    }
};