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.

Have you met this question in a real interview?

Yes

Example

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

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

Challenge

Do it in O(nlogn) time complexity.

class Solution {
public:
    /**
     * @param nums an integer array
     * @param target an integer
     * @return the difference between the sum and the target
     */
    int twoSumClosest(vector<int>& nums, int target) {
        // Write your code here

        if (nums.size() < 2) {
            return 0;
        }

        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1, diff = INT_MAX;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                return 0;
            }
            diff = min(diff, abs(target - nums[left] - nums[right]));
            if (nums[left] + nums[right] < target) {
                ++left;
            } else {
                --right;
            }
        }

        return diff;
    }
};