大家好，我是 程序员小熊 ，今天给大家带来一道亚马逊的面试题，即 LintCode 1478 · 最接近target的值 ，提供 双指针 的解题思路，供大家参考，希望对大家无论是刷题还是面试都有所帮助。

1478 · 最接近target的值

描述

给出一个数组，在数组中找到两个数，使得它们的和最接近目标值但不超过目标值，返回它们的和。

解题思路

思考： 如果数组是已按照 升序排列 的，那么这个题目是不是就很好做？那样的话，可以定义两个分别 指向数组的第一个元素和最后一个元素的指针，将两个指针指向的元素和与目标值 target 进行比较，然后再根据比较的结果，决定移动那一个指针 。

但是由于题目没有 告知数组是有序的 ，所以需要先对数组进行 排序 ，然后再采用 双指针 的策略去做。

注意点

1. 当 数组长度小于 2 时，不存在满足要求的结果，直接返回 -1；

2. 由于题目要求找到的两个数的和 最接近目标值但不超过目标值，因此只需要考虑找到的两个数的和 小于等于目标值 即可，不需要考虑大于的情况。

3. 定义变量 diff 用于保存当 target 大于等于 sum 时，target - sum 的值，并不断更新（取最小值），diff 初始值设置为 INT_MAX。

补充说明

注意点中的 第 3 点 中，diff 不断更新取最小值（diff = min(differ, target - sum)） 的原因是 题目要求在数组找到两个数的和最接近目标值但不超过目标值。

举栗

以 nums = [-18,-4,-6,13,4,4,16,-8]，target = 6 为例子，如下分析：

• 1、原始数组

 

• 2、排序之后

 

• 3、采用双指针 

• 4、定义 diff

• 5、查找过程如下 动态

 

Show me the Code

c++

 1 int closestTargetValue(int target, vector<int> &array) {
 2     int size = array.size();
 3     if (size < 2) {
 4         return -1;
 5     }
 6 
 7     sort(array.begin(), array.end());
 8     int left = 0, right = size - 1, diff = INT_MAX;
 9     while (left < right) {
10         int sum = array[left] + array[right];
11         if (sum > target) {
12             right--;
13         } else {
14             diff = min(diff, target - sum);
15             left++;
16         }
17     }
18     return diff == INT_MAX ? -1 : target - diff;
19 }

View Code

java

 1 int closestTargetValue(int target, int[] array) {
 2     int size = array.length;
 3     if (size < 2) {
 4         return -1;
 5     }
 6 
 7     Arrays.sort(array);
 8     int left = 0, right = size - 1, diff = Integer.MAX_VALUE;
 9     while (left < right) {
10         int sum = array[left] + array[right];
11         if (sum > target) {
12             right--;
13         } else {
14             diff = Math.min(diff, target - sum);
15             left++;
16         }
17     }
18     return diff == Integer.MAX_VALUE ? -1 : target - diff;
19 }

View Code