[lintcode] problem 533 – two sum – closest to target

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

public int (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;
}

[lintcode] problem 533 – two sum – closest to target

Example

No.1

No.2

Challenge

Code

近期文章

近期评论

标签

热门

文章归档

分类目录

功能