LeetCode 16 - 3Sum Closest

作者 QIFAN 日期 2017-01-12
LeetCode 16 - 3Sum Closest

原题链接: 16. 3Sum Closest


题干

给定一个含有 n 个数字的数组 S 和一个目标值 target ,找到数组中的三个数,使得这三个数之和最接近 target ,并返回三数之和。

前提:假设每个数组中有且仅有一个组合。

举例
输入: S = [-1, 2, 1, -4]target = 1
输出: 2
解释: -1 + 2 + 1 = 2 最接近 1 。

思路

大体思路与 15. 3Sum 一样,作如下几点修改:

  • 二叉搜索若没有找到,返回一个最接近的数
  • 增加一个变量 diff 来比较每次与 target 的差,如果 diff == 0 ,直接返回 target 。

容易混淆的地方在于二叉搜索返回最接近数的 base case 。假设数组为 S = [0, 2, 5] ,查找目标为 target ,排查到最后有下列三种情况:

  • target = -1 。最后 lo = 0 , hi = -1 。返回 lo 。
  • target = 3 。最后 lo = 2 , hi = 1 ,返回 a[lo] 与 a[hi] 中与 target 更接近的数,此例为 2 。
  • target = 6 。最后 lo = 3 , hi = 2 。返回 hi 。

结合这道题,第一种情况下 lo 不可能超出数组,因为 i 和 j 必定在前面。所以第一种情况可以与第二种情况一样判断,只要在主方法中再判断返回值是否与
j 相等即可。最后概括为两种情况:

  • lo > a.length - 1 , 返回 hi 。
  • 返回 a[lo] 与 a[hi] 中与 target 更接近的下标。

时间复杂度 $O(n^2logn)$

代码:

public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
// 初始化差
int diff = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
// 避免重复结果
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int lastj = 0;
for (int j = i + 1; j < nums.length - 1; j++) {
// 避免重复结果
if (j > i + 1 && nums[j] == nums[lastj]) {
continue;
}
int k = ambiguousBS(nums, target - (nums[i] + nums[j]), j + 1, nums.length - 1);
if (k == j) {
k = j + 1;
}
// System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
int currDiff = (nums[i] + nums[j] + nums[k]) - target;
if (Math.abs(currDiff) < Math.abs(diff)) {
diff = currDiff;
}
if (diff == 0) {
return target;
}
}
}
return target + diff;
}
// return the most close value in the array
private int ambiguousBS(int[] nums, int target, int lo, int hi) {
// base case: not found
if (lo > hi) {
if (lo > nums.length - 1) {
return hi;
}
if (Math.abs(nums[lo] - target) > Math.abs(nums[lo - 1] - target)) {
return lo - 1;
}
return lo;
}
int mid = lo + (hi - lo) / 2;
// base case: found
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
return ambiguousBS(nums, target, mid + 1, hi);
}
return ambiguousBS(nums, target, lo, mid - 1);
}