解
第一步，万年不变的查错。如果给的array是null或不够两个数，直接return 0
public int twoSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return 0;
}
...
}
看题，第一步想到暴力解法，即找到每一对数字的和，再从这一堆和里面，找出与target最接近的（打擂台）。这种方式为O(n^2)，因为每一个数字都要和除自己以外的数字算一次。怎样进行优化呢？题里有提示，挑战用O(nlogn)来解。O(nlogn)大部分就是排序，因为排序最低就是O(nlogn)。所以想到对array排序。
Arrays.sort(nums);
然后就是怎么利用一个已经排好序的数列。首先要有一个最低的差，minSumDiff。初始化为最大值，以为一会要用它来比小，所以第一次不管是什么数字，都不会比它大。再来两个pointer，一左一右。
int minSumDiff = Integer.MAX_VALUE;
int left = 0;
int right = nums.length - 1;
左右两个pointer同时开始向中间移动，如果需要数字之和变小，那就右边往左移。找到当前两个pointer指向的数字之和sum，以及跟target的差sumDiff。
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return 0;
}
int sumDiff = Math.abs(target - sum);
...
}
这里有可能出现一个edge case，sum跟target一样，即它们的差为0。当这个时候，我加了一个if statement，如果出现就直接返回，既然找到一样的了，后面就没有继续遍历的必要了。这里加不加都可以。如果数列里出现一个和跟target一样的，那么加了就比不加好。相反，如果没有，加了就不如不加。可以问面试官那种可能更大一点。
如果需要数字之和变大，那就左边往右移。移动的过程中，不断的进行打擂台，对比当前最低的接近差，如果比当前最低的低，那就把最低的改成现在的差。
minSumDiff = Math.min(minSumDiff, sumDiff);
然后如果当前的和小于target，那我们就去找下一个大一点的数，即右边pointer往左移。如果当前的和大于target，那我们就去找下一个小一点的数，即左边的pointer往右移。
if (sum < target) {
left++;
} else {
right--;
}
最后，返回当前最低的差即可。
return minSumDiff;
完整的code
public class Solution {
/*
* @param nums: an integer array
* @param target: An integer
* @return: the difference between the sum and the target
*/
public int twoSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int minSumDiff = Integer.MAX_VALUE;
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return 0;
}
int sumDiff = Math.abs(target - sum);
minSumDiff = Math.min(sumDiff, minSumDiff);
if (sum < target) {
left++;
} else {
right--;
}
}
return minSumDiff;
}
}
分析
时间复杂度
对array进行排序，为O(nlogn)。两个pointer遍历，为O(n)。所以总共的时间复杂度是O(nlogn)。
空间复杂度
只有个别的单个变量，所以空间复杂度是O(1)。
这道题我的思路和九章一样。应该是最优解。
