LintCode-三数之和 II

题目描述:

  给一个包含n个整数的数组S, 找到和与给定整数target最接近的三元组,返回这三个数的和。

注意事项

  只需要返回三元组之和,无需返回三元组本身

样例

  例如S = [-1, 2, 1, -4] and target = .  和最接近1的三元组是 -1 + 2 + 1 = 2.

 public class Solution {
/**
* @param numbers: Give an array numbers of n integer
* @param target : An integer
* @return : return the sum of the three integers, the sum closest target.
*/
public int threeSumClosest(int[] numbers ,int target) {
// 记录最小的差值
long minDiff = Long.MAX_VALUE;
// 记录最小差值对应的三个整数和
long result = 0;
// 每次求得的差值
long diff;
// 每次求得的三个整数的和
long sum; // 先对数组进行排序
Arrays.sort(numbers); // i表示假设取第i个数作为结果
for (int i = 0; i < numbers.length - 2; i++) {
// 第二个数可能的起始位置
int j = i + 1;
// 第三个数可能是结束位置
int k = numbers.length - 1; while (j < k) {
// 求当前三个数的和
sum = numbers[j] + numbers[k] + numbers[i];
// 当前和与目标和之间的差值
diff = Math.abs(target - sum); // 差值为0就直接返回
if (diff == 0) {
return (int) sum;
} // 如果当前的差值比之前记录的差值小
if (diff < minDiff) {
// 更新最小的差值
minDiff = diff;
// 更新最小差值对应的和
result = sum; // 以上的设置在下一次元素处理时生效
} // 和大于target
if (sum > target) {
k--;
}
// 和小于target
else {
j++;
}
}
} return (int) result;
}
}
上一篇:Linux 容器 vs 虚拟机 —— 谁更胜一筹


下一篇:Thread 线程简单例子