16. 3Sum Closest
给定一个长度大于3的整数阵列和一个数字target，求出最接近target的任意三数之和，
假定测资只存在恰好一解。
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
法一 暴力法
思路：
1.老子直接在你面前跑三层loop
Java Code：
class Solution {
public int threeSumClosest(int[] nums, int target) {
int closest = Integer.MAX_VALUE;
int res = 0;
for(int i = 0;i < nums.length;i++)
for(int j = i + 1; j < nums.length; j++)
for(int k = j + 1; k < nums.length; k++) {
int sum = nums[i] + nums[j] + nums[k];
int diff = Math.abs(target - sum);
if(diff < closest) {
res = sum;
closest = diff;
}
}
return res;
}
}
时间复杂度O(n^3) 安心信赖TLE
法二 双指标
思路：
1.题目要求与target最接近的sum，所以：
A + B + C = sum ==> 趋近于target
我们可以把他移项：
B + C = 趋近于target - A
该问题就会退化为在阵列里搜寻最接近 target 的 B + C
2.先把整个阵列排序，这样可以快速的取值且排除掉使用过的组合。
3.遍历阵列，把nums[i]当作第一个加数A，并从右取最大和最小值当B和C。
sum = A + B + C
4.依据状况移动指标，分两case：
若sum > target 表示我们要再拿更小 right