题目链接:https://leetcode-cn.com/problems/3sum-closest/

题目描述:

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

示例:

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

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

思路:

一句话解释:固定一个值,找另外两个值(双指针).

数组是已排好序,首先确定一个数,在左右指针运动过程中,记录与target绝对值差值最小的.

---

可以关注我的知乎专栏,了解更多解题方法!

代码:

python

class Solution:

    def threeSumClosest(self, nums: List[int], target: int) -> int:

        nums.sort()

        #print(nums)

        n = len(nums)

        res = float("inf")

        for i in range(n):

            if i > 0 and nums[i] == nums[i-1]:

                continue

            left = i + 1

            right = n - 1

            while left < right :

                #print(left,right)

                cur = nums[i] + nums[left] + nums[right]

                if cur == target:return target

                if abs(res-target) > abs(cur-target):

                    res = cur

                if cur > target:

                    right -= 1

                elif cur < target:

                    left += 1

        return res

java

class Solution {

    public int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);

        //int res = Integer.MAX_VALUE;

        int n = nums.length;

        int res = nums[0] + nums[1] + nums[n-1];

        for (int i = 0; i < n - 2; i++) {

            if (i > 0 && nums[i] == nums[i-1]) continue;

            int left = i + 1;

            int right = n - 1;

            while (left < right) {

                int cur = nums[i] + nums[left] + nums[right];

                if (cur == target) return target;

                if (Math.abs(res - target) > Math.abs(cur - target)) res = cur;

                if (cur > target) right -= 1;

                if (cur < target) left += 1;

            }

        }

        return res;

    }

}

c++

class Solution {

public:

    int threeSumClosest(vector<int>& nums, int target) {

        int n = nums.size();

        // c++ 排序

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

        int res = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++){

            if (i > 0 && nums[i] == nums[i-1]) continue;

            int left = i + 1;

            int right = n - 1;

            while (left < right){

                int cur = nums[i] + nums[left] + nums[right];

                if (cur == target) return target;

                if (abs(res - target) > abs(cur - target)) res = cur;

                if (cur > target) right -= 1;

                if (cur < target) left += 1;

            }

        }

        return res;

    }

};