描述
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
初次提交代码
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
new_nums = sorted(nums)
size = len(new_nums)
min_dis = 100000
ans = 0
dis_sum = {}
for i in range(size - 2):
left = i + 1
right = size - 1
while left < right:
tmp_sum = new_nums[i] + new_nums[left] + new_nums[right]
dis_sum[math.fabs(tmp_sum - target)] = tmp_sum
if tmp_sum > target:
right -= 1
elif tmp_sum < target:
left += 1
else:
dis_sum[0.0] = target
break
ans_list = sorted(dis_sum.iteritems(), key=lambda d: d[0])
# print ans_list
return ans_list[0][1]
提交结果，太慢！
思路分析及改进思考
输入列表排序之后从 0 ~ size - 2 逐个考虑每一个元素ai.left, right分别代表a[i+1,size - 1]两端的左右位置,left,right 不断逼近，将每一次的ai + a[left] + a[right] 记录下来，最后排个序找出最合适的结果。
Extra: python
1.字典排序
字典排序的想法是获取字典的元组列表，然后按照键值对元组列表进行排序
ans_list = sorted(dis_sum.iteritems(), key=lambda d: d[0])
可以这样来理解， key传入的参数就是sorted的第一个参数的类型，在这里就是一个元组，用lambda返回元组中的第一个元素。
2.python lambda
lambda x:x*x #就是匿名函数
