原题
找到两个数字使得他们和最接近target
样例
nums = [-1, 2, 1, -4],target = 4.
最接近值为 1
解题思路
- 对撞型指针问题，思路与Two Sum类似 O(n2) => O(n)
- 两个指针分别从数组的头跟尾向中间移动，相比于两次for循环，避免了不必要的扫描
完整代码
class Solution:
# @param {int[]} nums an integer array
# @param {int} target an integer
# @return {int} the difference between the sum and the target
def twoSumCloset(self, nums, target):
# Write your code here
nums.sort()
i, j = 0, len(nums) - 1
diff = sys.maxint
while i < j:
if nums[i] + nums[j] < target:
diff = min(diff, target - nums[i] - nums[j])
i += 1
else:
diff = min(diff, nums[i] + nums[j] - target)
j -= 1
return diff
