【Lintcode】533. Two Sum - Closest to target

题目地址：

https://www.lintcode.com/problem/two-sum-closest-to-target/description

给定一个数组$A$A，再给定一个数target，求所有数组中数对之和与target的差的绝对值最小的那个绝对值。

思路是排序数组后对撞双指针，同时不断更新得到的数对和与target之差的绝对值。如果两数之和小于target，那么左指针右移；如果大于target则右指针左移；若等于，则直接返回$0$0。代码如下：

import java.util.Arrays;

public class Solution {
    /**
     * @param nums: an integer array
     * @param target: An integer
     * @return: the difference between the sum and the target
     */
    public int twoSumClosest(int[] nums, int target) {
        // write your code here
        Arrays.sort(nums);
        
        int i = 0, j = nums.length - 1;
        int res = Integer.MAX_VALUE;
        
        while (i < j) {
            int sum = nums[i] + nums[j];
            res = Math.min(res, Math.abs(sum - target));
            if (sum < target) {
                i++;
            } else if (sum > target) {
                j--;
            } else {
                return 0;
            }
        }
        
        return res;
    }
}

时间复杂度$O(n\log n)$O(nlogn)，空间$O(1)$O(1)。

算法正确性证明与https://blog.csdn.net/qq_46105170/article/details/105886627类似。