Two Sum Closest

Given an array nums of n 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.

Challenge:

Do it in O(nlogn) time complexity.

Example:

Given array nums = [-1, 2, 1, -4], and target = 4.

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

Solution:

Same to Two Sum. Instead of finding the target, we find a number which is closest to the target. A closest variable is used to store the sum for each step.

Code:

public class Solution {
    /**
     * @param nums an integer array
     * @param target an integer
     * @return the difference between the sum and the target
     */
    public int twoSumCloset(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return Integer.MIN_VALUE;
        }
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        //be careful to use MIN_VALUE or MAX_VALUE, they have chance to overflow.
        int closest = nums[0] + nums[1];
        while (i < j) {
            int num = nums[i] + nums[j];
            if (target > num) {
                i++;
            } else {
                j--;
            }
            if (Math.abs(target - num) < Math.abs(target - closest)) {
                closest = num;
            }
        }
        return Math.abs(closest - target);
    }
}