【边学边敲边记】LeetCode007:最接近的三数之和
一、写在前面
最近在思考一个问题，也是一个读者问我的“你是如何使用最优解的？”，的确这是个很好的问题，当时我也是一楞，搪塞了几句，这个问题却被我深深的记着，我到底改怎么找到最优解(更优解)？单单凭我一个人显然力量不够，在学习了极客时间的《算法面试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 努力 ： 终有所获。