LeetCode50天刷题计划（Day 11—— 最接近的三数之和（8.40-10.00）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

第一次体验一次AC的快乐 只能说 实在是太爽了啊啊啊

一、题目

最接近的三数之和

给你一个长度为 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

二、思路

双指针法

这道题本质上仍是求三数之和，可以采用双指针法解题
首先每轮固定第一个值 i（具体操作是对列表遍历），然后第二个值的指针j指向i后第一个数，第三个值的指针k指向最后一个数，j与k同时向中间移动。（移动规则是，如果三者之和小于target，那么j向右移动使和增大，如果三者之和大于target，那么k向左移动使和减小）
在这种方法下，如果三者之和等于target，说明已经找到了最优的情况，此时无需再遍历固定i值了，直接输出即可
如果在此i值之下无法找到三者之和恰好等于target的情况，那么当j与k指针相遇时就是次优解，因为j与k的移动都是不断向和为target的方向靠拢的。此时只需要保存此轮次优解，与当前最小值比较（和与target相差最少）即可。
注：这里的“相差”可以用相减取绝对值来表示

复杂度分析

●时间复杂度: O(N^2)， 其中N是数组nums的长度。
首先需要O(N log N)的时间对数组进行排序，然后双重循环遍历i和j、k，一共是O(N^2)。
●空间复杂度: O(log N)。排序需要使用O(log N)的空间。
其实修改了输入的数组nums,如果看成使用了一个额外的数组存储了nums的副本并进行排序，此时空间复杂度为O(N)。

三、代码

python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        #将数组排序
        nums.sort() 
        #数组元素个数
        n=len(nums) 
        #保存绝对值和次优返回值
        min_abs=pow(10,5)
        result=0
        #遍历第一个数
        for i in range(n-2):
            #首尾指针，和最好为target-i
            j=i+1
            k=n-1
            #本轮最接近的一个，即有相等或ij碰面的时候
            near=0
            while(j<k):
                temp=nums[i]+nums[j]+nums[k]
                #最优情况
                if(temp == target):
                    #已经是最接近了，相等了
                    return temp 
                #没相等但jk已经挨着了，次优情况，与当前最小绝对值对比
                if(j+1 == k):
                    cur_abs=abs(target-temp)
                    if(cur_abs<min_abs):
                        min_abs=cur_abs
                        result=temp
                    #进入下个i循环
                    break 
                #都不是，继续移动指针
                if(temp<target):
                    j+=1
                elif(temp>target):
                    k-=1
        #输出
        return result