LintCode 533 [Two Sum Closest]

原题

找到两个数字使得他们和最接近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