L553 Two Sum Closest

Given an arraynumsofn_integers, find two integers in_nums_such that the sum is closest to a given number,_target.

Return the difference between the sum of the two integers and the target.

Given arraynums=[-1, 2, 1, -4], andtarget=4.

The minimum difference is1. (4 - (2 + 1) = 1).

Challenge

Do it in O(nlogn) time complexity.

还是2 pointer，先排序，然后还得用变量keep track of 全局min。这题因为是求closest，所以不能hashmap。

public int twoSumCloset(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        return Integer.MAX_VALUE;
    }

    Arrays.sort(nums);
    long min = Integer.MAX_VALUE;
    int i = 0;
    int j = nums.length - 1;
    while (i < nums.length && j >= 0 && i < j) {
        long sum = nums[i] + nums[j];
        long diff = Math.abs(target - sum);
        min = Math.min(min, diff);
        if (sum < target) {
            i++;
        } else if (sum > target){
            j--;
        } else {
            return 0;
        }
    }

    return (int)min;
}