描述
给出一个数组,在数组中找到两个数,使得它们的和最接近目标值但不超过目标值,返回它们的和。
思考: 如果数组是已按照 升序排列 的,那么这个题目是不是就很好做?那样的话,可以定义两个分别 指向数组的第一个元素和最后一个元素的指针,将两个指针指向的元素和与目标值 target 进行比较,然后再根据比较的结果,决定移动那一个指针 。
但是由于题目没有 告知数组是有序的 ,所以需要先对数组进行 排序 ,然后再采用 双指针 的策略去做。
注意点中的 第 3 点 中,diff 不断更新取最小值的原因是 题目要求在数组找到两个数的和最接近目标值但不超过目标值,diff = min(differ, target - sum)。
以 nums = [-18,-4,-6,13,4,4,16,-8],target = 6 为例子,如下分析:
1、原始数组
2、排序之后
3、采用双指针
4、定义 diff
5、查找过程如下 动图
int closestTargetValue(int target, vector<int> &array) {
int size = array.size();
if (size < 2) {
return -1;
}
sort(array.begin(), array.end());
int left = 0, right = size - 1, diff = INT_MAX;
while (left < right) {
int sum = array[left] + array[right];
if (sum > target) {
right--;
} else {
diff = min(diff, target - sum);
left++;
}
}
return diff == INT_MAX ? -1 : target - diff;
}
int closestTargetValue(int target, int[] array) {
int size = array.length;
if (size < 2) {
return -1;
}
Arrays.sort(array);
int left = 0, right = size - 1, diff = Integer.MAX_VALUE;
while (left < right) {
int sum = array[left] + array[right];
if (sum > target) {
right--;
} else {
diff = Math.min(diff, target - sum);
left++;
}
}
return diff == Integer.MAX_VALUE ? -1 : target - diff;
}