16. 最接近的三数之和

Difficulty
Medium
Tags
双指针
URL
https://leetcode-cn.com/problems/3sum-closest/
Star
给你一个长度为 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
  • 104 <= target <= 104

法 1 暴力搜索

思路
用三层循环去寻找三个值
题解
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        res = float("inf")
        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                for k in range(j+1, len(nums)):
                    temp = nums[i] + nums[j] + nums[k]
                    res = temp if abs(temp - target) < abs(res - target) else res
                    if res == target:
                        return res

        return res

法 2 双指针

思路
先对数组进行排序，然后外层循环选定一个值，内层循环再用相向双指针找另外两个值
题解
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = float("inf")
        # 固定一个值， 然后在内层采用双指针搜索
        for i in range(0, len(nums)-2):
            left, right = i + 1, len(nums)-1
            while left < right:
                temp = nums[i] + nums[left] + nums[right]
                res = temp if abs(temp- target) < abs(res-target) else res
                if temp > target:
                    right -= 1
                elif temp < target:
                    left += 1
                else:
                    return res
        return res