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;
}
}
上一篇: CentOS7.8 安装 OpenCV
下一篇: manuconfig错误 Unable to find the ncurses libraries or the required header files
推荐阅读
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
LeetCode - 1. Two Sum(8ms)
-
LeetCode_#1_两数之和 Two Sum_C++题解
-
Two Sum - 新手上路
-
LeetCode(62)-Two Sum
-
LeetCode:Two Sum浅析
-
00 | Two Sum
-
[LeetCode] 1. Two Sum 两数之和
-
167. Two Sum II - Input array is sorted [medium] (Python)
-
LintCode 139. Subarray Sum Closest