给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 示例:
输入: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
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum-closest 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
使用双指针,现将nums数组排序,然后i指向第一个元素依次到nums.size() - 2(防止越界) 定义left指针指向i + 1 定义right指针指向nums.size() - 1 若nums[i] + nums[left] + nums[right] < target。让left右移找到最适合的位置 反之让right左移
定义一个result = nums[0] + nums[1] + nums[2],如果后面有元素和target更接近则换成相应元素。
sum = nums[i] + nums[left] + nums[right]
if(abs(sum - target) < abs(result - target))
如果此三个数之和更接近target则将resule换成这三个元素
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int result = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.size() - 2; i++) {
int left = i + 1;
int right = nums.size() - 1;
while (left != right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return sum;
}
if(abs(sum - target) < abs(result - target))
result = sum;
if(sum > target) {
right--;
}
else {
left++;
}
}
}
return result;
}
};