简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
一、写在前面
最近在思考一个问题，也是一个读者问我的“你是如何使用最优解的？”，的确这是个很好的问题，当时我也是一楞，搪塞了几句，这个问题却被我深深的记着，我到底改怎么找到最优解(更优解)？单单凭我一个人显然力量不够，在学习了极客时间的《算法面试40讲》后，我想出了几个方法：
1.[最主要的方法]靠大家，现在微信公众号7000多关注，就算有4000多僵尸粉，2000多非算法爱好者，那也还得有1000多的人可以和我一起吧？希望看到这篇推文的读者能留言：支持老表 或者 自己想说的话；
2.[自己百度谷歌]没得错，要自己单纯靠脑袋想出最优解还是比较难的，所以要学会百度谷歌，学习别人的方法，“择其善者而从之，不善者而改之”；
3.[转战LeetCode英文网站]对的，学习了《算法面试40讲》后，老师有讲LeetCode题，我突然发现英文网站除了英文不好外，讨论、提交等等都比中文网站好很多，所以后面可能转战LeetCode英文网站，也可以提升一下自己的英文水平。
LeetCode 第六题三数之和传输门：LeetCode006:三数之和
今天给大家分享的是LeetCode 数组与字符串 第七题：最接近的三数之和，为面试而生，期待你的加入。
二、今日题目
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例:
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
三、 分析
看到这个题目，我马上想到上一题三数之和，思路也和上一题差不多，一层for循环加一层while循环：
我的基本分析
四、解题
- 我的方法：
• for+while，时间复杂度：O(n^2) class Solution(object): def threeSumClosest(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ # 距离 distance_t = 10000 # 返回结果 result_sum = 0 # 1.排序，方便比较 nums.sort() # 一层：找出头 for i in range(len(nums)-2): left = i + 1 right = len(nums) - 1 first = nums[i] # 二层：左右夹击 while left < right: second = nums[left] third = nums[right] sum = first + second + third abs_flag = abs(sum - target) if abs_flag == 0: # 最接近 return target elif abs_flag < distance_t: # 距离变小，记录当前sum和distance_t result_sum = sum distance_t = abs_flag if sum > target: right -= 1 # 左移变大 else: left += 1 # 右移变小 return result_sum
- 提交结果
提交结果
测试数据：125组
运行时间：68ms
击败人百分比:79.62%
从上面运行结果可以看出，这种查找方法应该是比较常见的一种方法，提交结果都聚集在这块。
为了找到更好的方法，我在LeetCode英文官网上找了一圈，发现除了我的方法外，主要了下面两种方法：
- 排序+双指针（和我的方法是一个道理，提交结果没有直接利用列表遍历好）
- 枚举+ 分类比较(下面主要给大家介绍学习一下这种方法)
这里为大家好好介绍一下大牛方法：
- 大牛方法
- 思路解析
- 代码
class Solution(object): def threeSumClosest(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ nums.sort() length = len(nums) closest = [] for i, num in enumerate(nums[0:-2]): l, r = i + 1, length - 1 # different with others' solution if num + nums[r] + nums[r - 1] < target: # 最大 closest.append(num + nums[r] + nums[r - 1]) elif num + nums[l] + nums[l + 1] > target: # 最小 closest.append(num + nums[l] + nums[l + 1]) else: while l < r: # 左右混合 closest.append(num + nums[l] + nums[r]) if num + nums[l] + nums[r] < target: # 数小，右移 l += 1 elif num + nums[l] + nums[r] > target: # 数大，左移 r -= 1 else: # 相等 return target # 根据与target的距离排序，从小到大 closest.sort(key=lambda x: abs(x - target)) return closest[0]
- 提交结果
大牛提交结果
测试数据：125组
运行时间：28ms
击败人百分比:99.09%
五、疑惑
数据结构还是很深奥的，选择上，设计上，都是得好好学习，包括算法的思想上，逻辑选择上，希望一个月，两个月，更久后，我能越来越熟练,越来越厉害，希望大家的坚持都能有所收获。
六、结语
坚持 and 努力 ： 终有所获。
