1.题目基本信息

1.1.题目描述

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

返回这三个数的和。

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

1.2.题目地址

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

2.解题方法

2.1.解题思路

排序+双指针

2.2.解题步骤

第一步，将nums进行升序排列

第二步，固定指针i

• 2.1.剪枝。i>0 and nums[i]==nums[i-1]情况，此时的情况在i-1时已经枚举过，所以不必重复

第三步，使用双指针求nums[i+1,length)范围中最接近target-nums[i]的两数之和

• 3.1.头指针start剪枝。剪除重复讨论的情况

• 3.2.尾指针end左移进行收缩

• 3.3.此时的sum<=target，判断当前组合的和是否是更优解，并更新维护变量

  • 3.3.1.end处讨论

  • 3.3.1.end+1处讨论

• 3.4.右移头指针

3.解题代码

python代码

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 思路：排序+双指针
        n = len(nums)
        result, diff = 0, inf
        # 第一步，将nums进行升序排列
        nums.sort()
        # 第二步，固定指针i
        for i in range(n):
            # 2.1.剪枝。i>0 and nums[i]==nums[i-1]情况，此时的情况在i-1时已经枚举过，所以不必重复
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 第三步，使用双指针求nums[i+1,length)范围中最接近target-nums[i]的两数之和
            start, end = i + 1, n - 1
            while start < end:
                # 3.1.头指针start剪枝。减除重复讨论的情况
                if start > i + 1 and nums[start] == nums[start - 1]:
                    start += 1
                    continue
                # 3.2.尾指针end左移进行收缩
                while start < end and nums[start] + nums[end] + nums[i] > target:
                    end -= 1
                # 3.3.此时的sum<=target，判断当前组合的和是否是更优解，并更新维护变量
                if start != end and abs(nums[start] + nums[end] + nums[i] - target) < diff:
                    # 3.3.1.end处讨论
                    result = nums[start] + nums[end] + nums[i]
                    diff = abs(nums[start] + nums[end] + nums[i] - target)
                if start != end + 1 and end + 1 < n and abs(nums[start] + nums[end + 1] + nums[i] - target) < diff:
                    # 3.3.1.end+1处讨论
                    result = nums[start] + nums[end + 1] + nums[i]
                    diff = abs(nums[start] + nums[end + 1] + nums[i] - target)
                # 3.4.右移头指针
                start += 1
        return result

4.执行结果