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).

/*

The naive way is to find every two-element pair and calculate the difference between the sum and target. Save the minimum difference.

time:O(n^2), space:O(1)

One better way is to sort the array first and then use two pointers.

time: O(nlogn), space: O(1)

*/

public class Solution {

    public int twoSumCloset(int[] nums, int target) {

        int minDiff = Integer.MAX_VALUE;

        if (nums == null || nums.length < 2) {

            return minDiff;

        }

        Arrays.sort(nums);

        int start = 0;

        int end = nums.length - 1;

        while (start < end) {

            int diff = nums[start] + nums[end] - target;

            if (diff > 0) {

                end--;

            } else if (diff < 0) {

                start++;

            } else {

                return 0;

            }

            if (Math.abs(diff) < minDiff) {

                minDiff = Math.abs(diff);

            }

        }

        return minDiff;

    }

}