P164 求和最接近目标值的三个数

描述#

这个题目说的是，给你一个整数数组和一个目标值，你要在数组中找到三个整数，使它们的和最接近目标值。然后返回这三个整数的和。

注意，假设给你的数组都有一个唯一解。

比如说，给你的数组是：
[-1, 2, -1, -4]
给你的目标值是 1。在这个数组中，求和后最接近目标值 1 的三个数字是：
[-1, 2, -1]
它们相加等于 0，因此你要返回 0。
再比如说，给你的数组不变，但是目标值改成 -6。
在这个数组中，正好有三个数的和等于 -6，它们是：
[-1, -1, -4]
因此它们的和 -6 就是最接近目标值的数字，返回它即可。

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public int threeSumClosest(int[] nums, int target) {
    int result = 0, min = Integer.MAX_VALUE;
    Arrays.sort(nums);

    for (int k = nums.length-1; k >= 2; --k) {
      int i = 0, j = k-1;
      while (i < j) {
        int sum = nums[i] + nums[j] + nums[k];
        if (sum == target) return sum;
        else if (sum < target) ++i;
        else --j;
        int diff = Math.abs(target - sum);
        if (diff < min) {
          result = sum;
          min = diff;
        }
      }
    }
    return result;
  }

}