Problem Definition:
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).
Solution:
结构基本上跟#15一样样的。只是这里要求最接近的一个和,即求 sum,使得 | target-sum | 最小。
绝对值的取值,最小也就是0了,所以一旦找到这样一个sum==target,就可以直接退出了。在OJ上一跑,发现测试的例子里还真不少这种,存在某三个数,其和刚好是target这么大。
1 # @param {integer[]} nums 2 # @param {integer} target 3 # @return {integer} 4 def threeSumClosest(nums, target): 5 nums.sort() 6 first=0 7 finalFirst=len(nums)-3 8 rightBound=len(nums)-1 9 minGap=sys.maxint 10 klz=0 11 while first<=finalFirst: 12 lft=first+1 13 rgt=rightBound 14 nf=nums[first] 15 while lft<rgt: 16 nl=nums[lft] 17 nr=nums[rgt] 18 thr=nf+nl+nr 19 gap=abs(thr-target) 20 if gap<minGap: 21 minGap=gap 22 klz=thr 23 if thr>target: 24 rgt-=1 25 elif thr<target: 26 lft+=1 27 else: #crux 28 return klz 29 30 while first<=finalFirst and nums[first]==nf: 31 first+=1 32 return klz