[LintCode] Problem 533 - Two Sum - Closest to target

Posted on | In ,

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 absolute value of difference between the sum of the two integers and the target.

Example

No.1

Input: nums = [-1, 2, 1, -4] and target = 4

Output: 1

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

No.2

Input: nums = [-1, -1, -1, -4] and target = 4

Output: 6

Explanation:
The minimum difference is 6. (4 - (- 1 - 1) = 6).

Challenge

Do it in O(nlogn) time complexity.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int twoSumClosest(int[] nums, int target) {
    int result = Integer.MAX_VALUE;

    if (nums == null || nums.length < 2)
        return result;

    int left = 0;
    int right = nums.length - 1;

    Arrays.sort(nums);

    while (left < right) {
        int sum = nums[left] + nums[right];
        result = Math.min(result, Math.abs(sum - target));

        if (sum < target)
            left++;
        else if (sum > target)
            right--;
        else
            return result;
    }

    return result;
}