2 Sum Closest

Question

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

Analysis

与3 sum closest问题相似,通过先对数组排序,再用两个指针的方法,可以满足 O(nlogn) + O(n) ~ O(nlogn)的时间复杂度的要求
不同的是这里要返回的是diff,所以只用记录minDiif即可。

Solution

public class Solution {
/**
* @param nums an integer array
* @param target an integer
* @return the difference between the sum and the target
*/
public int twoSumCloset(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return -1;
}
if (nums.length == 2) {
return target - nums[0] - nums[1];
}
Arrays.sort(nums);
int pl = 0;
int pr = nums.length - 1;
int minDiff = Integer.MAX_VALUE;
while (pl < pr) {
int sum = nums[pl] + nums[pr];
int diff = Math.abs(sum - target);
if (diff == 0) {
return 0;
}
if (diff < minDiff ) {
minDiff = diff;
}
if (sum > target) {
pr--;
} else {
pl++;
}
}
return minDiff;
}
}
Last modified 3yr ago