首页 > 学院 > 开发设计 > 正文

3Sum Closest

2019-11-06 09:23:24
字体:
来源:转载
供稿:网友

leetcode第16题,和3sum题类似,但是思路很不一样,要求在数组中找出三个数,使得三个数的和最接近目标数。

这道题最明显的解法是双指针法,主要思路是,先对数组排序,之后从头开始遍历,遍历过程中使用双指针,一个指向开头,一个指向结尾,三个数加和,求取和目标数的差距,如果差距为正,说明加和过大,应该向小的方向调整,所以end指针应该向左移动,同理,如果差距小于0,start指针向右移动,因为数组已经有序,这样移动肯定可以满足调整的要求。

注意合适使用abs,只有在衡量差距与最小差距的相对大小时候,才使用abs。

def threeSumClosest(self, nums, target): nums.sort() n = len(nums) minNum = 9999999 for i in range(n): start = i+1 end = n-1 while start < end: tmp = nums[i]+nums[start]+nums[end]-target if abs(tmp) < abs(minNum): minNum = tmp if minNum == 0: return target elif tmp < 0: start += 1 elif tmp > 0: end -= 1 return minNum+target
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表