【刷题笔记6】最接近的三数之和

题目来源LeetCode 16.最接近的三数之和
本贴为个人日常刷题笔记，有任何问题欢迎随时交流~
该题类别是：数组

一、题目

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

二、提示

$\le nums.length \le 10^3$
$-10^3 \le nums[i] \le 10^3$
$-10^4 \le target \le 10^4$

三、思考

题限思考

数组无序
三个整数与target最接近
返回三数和
边界问题：若len(nums) <= 3，返回数组之和
与leetcode15类似，考虑使用排序+双指针，注意区别
- 不用记录重复，但可以避免重复
- 记录最接近的值
小案例：

nums = [-1, 2, 1, -4]

target = 1

sort_nums = [-4, -1, 1, 2]

解法思考

排序+双指针
解题思路：
- 初始化res = target - sum(nums[:3])
- nums进行排序
- 固定左指针i，从0开始到len(nums) - 2停止
- 中间指针j，从i+1开始；右指针k，从len(nums) - 1开始，j < k
  - 记录当前三个指针指向值之和：temp = nums[i] + nums[j] + nums[k]
  - 记录差距：diff = target - temp
  - 当 diff = 0 时，return temp
  - 当 diff > 0 时，说明temp小了
    - 若 diff 小于 abs(res)，res = diff
    - j += 1
    - 去重复
  - 当 diff < 0时，说明temp大了
    - 若diff 小于-abs(res)，res = diff
    - k -= 1
- 返回 target - res

四、解法（双指针）

# 绝对值优化思路
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = target - sum(nums[:3])
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                temp = nums[i] + nums[j] + nums[k]
                diff = target - temp
                if diff == 0:
                    return target
                elif diff > 0:
                    if diff < abs(res):
                        res = diff
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                else:
                    if diff > - abs(res):
                        res = diff
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
        return target - res

# 另外的思路
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        size = len(nums)
        # 特判
        if size < 3:
            return []
        # 初始化，因为找最小值，因此把初始值设置成实数的最大值
        diff = float('inf')

        # 排序是前提
        nums.sort()

        for i in range(size - 2):
            # 常见的剪枝操作
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 双指针：指针对撞
            left = i + 1
            right = size - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]

                if abs(s - target) < diff:
                    diff = abs(s - target)
                    res = s

                # 不管是变小还是变大，尝试的作用是让 s 与 target 更接近
                # 即 s 与 target 的绝对值之差越来越小
                if s > target:
                    # 如果大了，尝试右边界收缩一格，让 target 变小
                    right -= 1
                elif s < target:
                    # 如果小了，尝试左边界收缩一格，让 target 变大
                    left += 1
                else:
                    # 如果已经等于 target 的话, 肯定是最接近的，根据题目要求，返回这三个数的和
                    return target
        return res