leetcode 16. 最接近的三数之和
给定一个包括n个整数的数组nums和一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。
题解：
1.一个整数数组nums和目标值target
2.找出三个整数，和与target最接近
3.返回这个和，答案唯一
4.nums长度最小为3，这三个数不要求连续
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
解题思路：
-
思路与15. 三数之和一样在找数的过程，都是在找三个数字
-
因为数组无序，先进行排序方便找三个数比较
-
如果原本数组长度为3，直接返回这三个数的和
-
数组排序后，记录前三个数的和为基准
-
下标从1开始，确定三数中的一个数
-
把数组中剩余的数看做一个从小到大排列的整体，设置前后指针并从两端往里取数，这里与15. 三数之和取数过程一样，比较基准与新三数和与target的距离，新三数和更近的话更新基准
-
如果值大于target，则右指针往左移动，降低和
-
值小于target，左指针往右移动，增大和
-
等于target，则为结果答案
C/C++题解：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());//对整个数组排序
//数组长度大于等于3，等于3时直接返回
int res = nums[0] + nums[1] + nums[2];
if(nums.size() == 3) return res;
for(int i=0;i<nums.size();i++) {//前后双指针
int start = i+1, end = nums.size() - 1;
while(start < end) {//与三数之和一样，选定一个i在剩余部分两端试数字
int sum = nums[start] + nums[end] + nums[i];
if(abs(target - sum) < abs(target - res))
res = sum; //如果新的三数更接近target,结果为sum
if(sum > target)//因为是从小到大排序
end -= 1;//新和大于target则右边数选的大，后指针往前走
else if(sum < target)
start += 1;//相反，小于就左指针往后走
else //等于则差0,直接是答案
return res;}}
return res;}};
Debug结果：
Java题解：
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);//对整个数组排序
//数组长度大于等于3，等于3时直接返回
int res = nums[0] + nums[1] + nums[2];
if(nums.length == 3) return res;
for(int i=0;i<nums.length;i++) {//前后双指针
int start = i+1, end = nums.length - 1;
while(start < end) {//与三数之和一样，选定一个i在剩余部分两端试数字
int sum = nums[start] + nums[end] + nums[i];
if(Math.abs(target - sum) < Math.abs(target - res))
res = sum; //如果新的三数更接近target,结果为sum
if(sum > target)//因为是从小到大排序
end -= 1;//新和大于target则右边数选的大，后指针往前走
else if(sum < target)
start += 1;//相反，小于就左指针往后走
else //等于则差0,直接是答案
return res;}}
return res;}}
Debug结果：
Python题解：
class Solution(object):
def threeSumClosest(self, nums, target):
""":type nums: List[int]:type target: int:rtype: int"""
nums.sort() #对整个数组排序
#数组长度大于等于3，等于3时直接返回
res = nums[0] + nums[1] + nums[2]
if len(nums) == 3: return res
for i in range(len(nums)):#前后双指针
start, end = i+1, len(nums) - 1
while start < end: #与三数之和一样，选定一个i在剩余部分两端试数字
sumVal = nums[start] + nums[end] + nums[i]
if abs(target - sumVal) < abs(target - res):
res = sumVal #如果新的三数更接近target,结果为sum
if sumVal > target: #因为是从小到大排序
end -= 1 #新和大于target则右边数选的大，后指针往前走
elif sumVal < target:
start += 1 #相反，小于就左指针往后走
else: #等于则差0,直接是答案
return res
return res
Debug结果：
更多题解移步公众号免费获取