Two Sum Closest

LintCode-533.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.

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

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

Do it in O(nlogn) time complexity.

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 == 0) {
            return 0;
        }
        
        Arrays.sort(nums);
        int low = 0, high = nums.length - 1;
        int diff = Integer.MAX_VALUE;
        
        while (low < high) {
            int sum = nums[low] + nums[high];
            
            if (sum > target) {
                high--;
            } else {
                low++;
            }
            
            diff = Math.min(diff, Math.abs(sum - target));
        }
        
        return diff;
    }
}

Hope this helps,
Michael