LeetCode 最接近的三数之和 排序+双指针+剪枝优化

原题链接：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题面：

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

返回这三个数的和。

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

示例 1：

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

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

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

解题思路：

和另外两双指针题三数之和、四数之和类似，不多赘述。

代码（CPP）：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans = 999999;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; i++) {
            // 优化
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] + nums[i + 1] + nums[i + 2] > target) {
                if (abs(nums[i] + nums[i + 1] + nums[i + 2] - target) < abs(ans - target)) {
                    ans = nums[i] + nums[i + 1] + nums[i + 2];
                }
                break;
            }
            if (target > 0 && nums[i] - target > ans - target) {
                break;
            }
            if (target < 0 && nums[i] > 0 && nums[i] - target > ans - target) {
                break;
            }
            if (nums[i] + nums[n - 2] + nums[n - 1] < target) {
                if (abs(nums[i] + nums[n - 2] + nums[n - 1] - target) < abs(ans - target)) {
                    ans = nums[i] + nums[n - 2] + nums[n - 1];
                }
                continue;
            }

            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == target) {
                    return sum;
                }
                if (sum > target) {
                    r--;
                } else {
                    l++;
                }
                if (abs(sum - target) < abs(ans - target)) {
                    ans = sum;
                }
            }
        }
        return ans;
    }
};

文章来源地址https://uudwc.com/A/Mx3Y5