# 引言
题目链接：https://leetcode.com/problems/3sum-closest/description/
# 题目大意
给出一个包含 n 个整数的数组 nums 和一个目标数字 target, 在数组中找到三个整数使得它们的总和最接近目标 target, 输出这个最接近目标值的数字
- Example
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
# 题解
这题其实是第 15 题的变种，相信看了这篇题解举一反三很容易能拿下这题，LeetCode:15.3Sum 题解，Click Here!
第 15 题是找到所有三个数的和等于 0 的组合，这题是找到三个数的和接近目标值，其实除了返回的结果不同整个过程都是类似的，只需要在 15 题的判断条件上进行修改即可，判断条件修改如下
由于数组有序，根据当前选取三个数字的和和目标值比较，大于目标值，第三个数字从剩余数组从后往前选取，小于目标值，第二个数字从剩余数组从前往后选取，每次选定三个目标后将选取数字的和和目标值差值比较，更新更小差值的数组和即可
int curSum = nums[i] + nums[midIndex] + nums[lastIndex];
if (curSum == target) return target;
else if (curSum > target) --lastIndex;
else ++midIndex;
retAns = abs(retAns - target) < abs(curSum - target) ? retAns : curSum;
# 复杂度
时间复杂度 O(n^2)
空间复杂度 O(1)
# AC 代码
c++ 版本
class Solution | |
{ | |
public: | |
int threeSumClosest(vector<int> &nums, int target) | |
{ | |
int retAns = 0x3f3f3f3f; | |
const int len = nums.size(); | |
std::sort(nums.begin(), nums.end()); | |
for (int i = 0; i < len - 2; ++i) | |
{ | |
if (i > 0 && nums[i] == nums[i - 1]) | |
{ | |
continue; | |
} | |
int midIndex = i + 1; | |
int lastIndex = len - 1; | |
while (midIndex < lastIndex) | |
{ | |
int curSum = nums[i] + nums[midIndex] + nums[lastIndex]; | |
if (curSum == target) | |
{ | |
return target; | |
} | |
else if (curSum > target) | |
{ | |
--lastIndex; | |
while (midIndex < lastIndex && nums[lastIndex + 1] == nums[lastIndex]) | |
{ | |
--lastIndex; | |
} | |
} | |
else | |
{ | |
++midIndex; | |
while (midIndex < lastIndex && nums[midIndex - 1] == nums[midIndex]) | |
{ | |
++midIndex; | |
} | |
} | |
retAns = abs(retAns - target) < abs(curSum - target) ? retAns : curSum; | |
} | |
} | |
return retAns; | |
} | |
}; |
go 版本
func intAbs(x int) int { | |
if x < 0 { | |
return -x | |
} | |
return x | |
} | |
func threeSumClosest(nums []int, target int) int { | |
retAns, lens := 0x3f3f3f3f, len(nums) | |
sort.Sort(sort.IntSlice(nums)) | |
for i := 0; i < lens-2; i++ { | |
if i > 0 && nums[i] == nums[i-1] { | |
continue | |
} | |
midIndex, lastIndex := i+1, lens-1 | |
for midIndex < lastIndex { | |
curSum := nums[i] + nums[midIndex] + nums[lastIndex] | |
if curSum == target { | |
return target | |
} else if curSum > target { | |
lastIndex-- | |
for midIndex < lastIndex && nums[lastIndex+1] == nums[lastIndex] { | |
lastIndex-- | |
} | |
} else { | |
midIndex++ | |
for midIndex < lastIndex && nums[midIndex-1] == nums[midIndex] { | |
midIndex++ | |
} | |
} | |
if intAbs(curSum-target) < intAbs(retAns-target) { | |
retAns = curSum | |
} | |
} | |
} | |
return retAns | |
} |
