T16. 3Sum Closest【Medium】
題目
給一個(gè)有 n 個(gè)整數(shù)的數(shù)組 S，找到 S 中的三個(gè)數(shù)骄瓣，使得這三個(gè)數(shù)的和最接近傳入的target(目標(biāo)數(shù))停巷。并返回這三個(gè)數(shù)的 sum(和)。你何以假設(shè)每個(gè)輸入都有一個(gè)確切的解答榕栏。
舉個(gè)例子畔勤，如果給出數(shù)組 S = [-1, 2, 1, -4],并且 target(目標(biāo)數(shù)) = 1
最接近的 sum 是 2.（-1 + 2 + 1 = 2）
思路
具體可以看代碼注釋~
代碼
代碼取自 Top Solution，稍作注釋
public int threeSumClosest(int[] num, int target) {
//初始一個(gè)result
int result = num[0] + num[1] + num[num.length - 1];
//給num排序
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int start = i + 1, end = num.length - 1;
//在while中num[i]是一定的扒磁，選出的是i時(shí)庆揪，i后面的數(shù)和i能組成的離target最近的sum
while (start < end) {
int sum = num[i] + num[start] + num[end];
//sum>target要減小sum,因?yàn)榕藕眯蛄耍詄nd--
if (sum > target) {
end--;
} else { //sum<=target時(shí)同理
start++;
}
//若相差小渗磅，則更新result值
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
}
}
return result;
}
補(bǔ)充
這題發(fā)現(xiàn)當(dāng)從數(shù)組里面挑選數(shù)相加為一個(gè)目標(biāo)數(shù)是時(shí)嚷硫，可以用先把數(shù)組排序，從兩邊往里相加湊數(shù)這樣的方法始鱼。
之前寫(xiě)的類似的解法：T15 3Sum
