描述
給一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 S, 找到和與給定整數(shù) target 最接近的三元組丽啡，
返回這三個(gè)數(shù)的和谋右。
注意事項(xiàng)
只需要返回三元組之和，無(wú)需返回三元組本身
樣例
例如 S = [-1, 2, 1, -4] and target = 1. 和最接近 1 的三元組是 -1 + 2 + 1 = 2
挑戰(zhàn)
O(n^2) 時(shí)間, O(1) 額外空間
注意
- 如果需要返回三元組补箍，就需要像三數(shù)之和一樣定義函數(shù)改执，定義results，進(jìn)行形參傳遞
- 可以先排序坑雅，因?yàn)槟J(rèn)的排序算法是歸并排序
思路
三數(shù)實(shí)際上就是兩根指針再加上for循環(huán)
代碼
public class Solution {
/*
* @param numbers: Give an array numbers of n integer
* @param target: An integer
* @return: return the sum of the three integers, the sum closest target.
*/
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return -1;
}
Arrays.sort(nums);
// 初值
int bestSum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
int start = i + 1;
int end = nums.length - 1;
// sum值要放到while循環(huán)里,不然start和end改變時(shí)sum辈挂，不發(fā)生變化
while (start < end) {
int sum = nums[i] + nums[start] + nums[end];
if (Math.abs(sum - target) < Math.abs(bestSum - target)) {
bestSum = sum;
}
if (sum < target) {
start++;
// 此處如果寫成 if (sum > target)，如果數(shù)組只有三個(gè)元素出現(xiàn) sum == target 情況會(huì)卡住
} else {
end--;
}
}
}
return bestSum;
}
}
