首页 > 代码库 > 3Sum Closest
3Sum Closest
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).
分析：
问题是从数列中找到3个数其和与给定值最接近。只要给出最终的和即可。
从解法上来讲比3Sum要简单，因为不用处理所有情况，也无需排序去重。但是通过dict映射的解法不再适合，因为求的值是未知的，看了一些网络上的讨论，基本都是同一种算法。无论用哪种编程语言，写出的代码都很相似。
class Solution: # @return an integer def threeSumClosest(self, num, target): num.sort() diff = 10 ** 8 ret = diff for i in range(len(num)): start = i + 1 end = len(num) - 1 while start < end: val = num[start] + num[i] + num[end] tmp = abs(target - val) if tmp < diff: diff = tmp ret = val if val == target: return val elif val < target: start += 1 else: end -= 1 return retif __name__ == ‘__main__‘: s = Solution() assert s.threeSumClosest([-1, 2, 1, -4], 1) == 2 assert s.threeSumClosest([1, 1, 1, 1], 0) == 3 assert s.threeSumClosest([1, 1, 1, 1], -100) == 3 print ‘PASS‘
小结：
从算法角度而言上面的代码是优雅的，这种计算问题即使是Python也很难做到在可读性和稳定性上明显优于其它语言实现。
3Sum Closest
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。