16. 3Sum Closest
16. 3Sum Closest
难度：Medium
内容
原题链接：https://leetcode.com/problems/3sum-closest
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
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).
思路
先排序，遍历第一个数，第二和第三个数通过双指针查找，转化为2sum closest的问题。如果遇到和等于target的三个数，直接返回target。
代码
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
std::sort(nums.begin(), nums.end());
int min_distance{INT_MAX}, sum{0}, cur_sum{0};
for (auto it = nums.cbegin(); it != nums.cend(); ++it)
for (auto left_idx = std::next(it), right_idx = std::prev(nums.cend()); left_idx < right_idx; cur_sum > target ? --right_idx : ++left_idx) {
cur_sum = *it + *left_idx + *right_idx;
auto cur_distance = std::abs(cur_sum - target);
if (cur_sum == target)
return target;
else if (cur_distance < min_distance) {
min_distance = cur_distance;
sum = cur_sum;
}
}
return sum;
}
};
