Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给一堆数字,第15题是要输出加和正好等于目标数值的所有三个数的三元组,本题是要输出最接近目标数值的三个数之和,默认只有一个答案,用了和第15题类似的思路

先sort list,枚举第一个数i=1~n-2,然后设置两个游标,左边从i+1向右,右边从n向左,更新如果三个数之和于目标值差距,如果三数之和小于目标值,第一个游标右移,否则第二个右边左移

Runtime: 1781 ms, faster than 78.79% of Python online submissions for 3Sum Closest.
Memory Usage: 13.5 MB, less than 52.25% of Python online submissions for 3Sum Closest.

 1 #16
 2 
 3 class Solution(object):
 4     def threeSumClosest(self, nums, target):
 5         """
 6         :type nums: List[int]
 7         :type target: int
 8         :rtype: int
 9         """
10         nums.sort()
11         min_diff = 60001
12         for i in range(len(nums)):
13             pos1 = i + 1
14             pos2 = len(nums) - 1
15             while pos1 < pos2:
16                 t_sum = nums[pos1] + nums[pos2] + nums[i]
17                 if abs(target - t_sum) < min_diff:
18                     min_diff = min(min_diff, abs(target - t_sum))
19                     ans = t_sum
20                 if abs(target - t_sum) == 0:
21                     return target
22                 if target > t_sum:
23                     pos1 += 1
24                 else:
25                     pos2 -= 1
26         return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理