欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Two Sum - Closest to target

程序员文章站 2022-03-11 22:51:37
...

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

Example1

Input:  nums = [-1, 2, 1, -4] and target = 4
Output: 1
Explanation:
The minimum difference is 1. (4 - (2 + 1) = 1).

Example2

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.

思路:同向双指针,更新diff即可;

public class Solution {
    /**
     * @param nums: an integer array
     * @param target: An integer
     * @return: the difference between the sum and the target
     */
    public int twoSumClosest(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return -1;
        }
        Arrays.sort(nums);
        int i = 0; int j = nums.length - 1;
        int diff = Integer.MAX_VALUE;
        while(i < j) {
            int sum = nums[i] + nums[j];
            if(sum == target) {
                return 0;
            } else if(sum > target) {
                if(sum - target < diff) {
                    diff = sum - target;
                }
                j--;
            } else { // sum < target;
                if(target - sum < diff) {
                    diff = target - sum;
                }
                i++;
            }
        }
        return diff;
    }
}

 

相关标签: Two pointers