3Sum最接近C ++
假设我们有一个具有n个整数和一个目标的nums数组。我们必须找到三个整数，以使总和最接近目标。我们将返回三个整数的和。我们可以假设每个输入将只有一个解决方案。因此，如果给定数组类似于[-1,2,1，-4]并且目标为1，则三元组将为[-1,2,1]，它的最接近总和为2。
为了解决这个问题，我们将遵循以下步骤-
对数组nums进行排序，ans：=0，diff：=Infinity，n：=nums的大小
对于i，范围为0至n–1
temp：=nums[left]+nums[right]+nums[i]
如果|target–temp|<diff，然后是ans：=temp和diff：=|target–temp|
如果temp=目标，则返回temp，否则返回temp>target，然后向右减小1，否则向左增大1
左：=i+1，右：=n–1
而左<右
返回ans
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = 0;
int diff = INT_MAX;
int n = nums.size();
for(int i = 0; i < n; i++){
int left = i + 1;
int right = n - 1;
while(left < right){
int temp = nums[left] + nums[right] + nums[i];
if(abs(target - temp) < diff){
ans = temp;
diff = abs(target - temp);
}
if(temp == target)return temp;
else if(temp > target) right--;
else left++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {-1,2,1,-4};
cout << ob.threeSumClosest(v, 1);
}输入值
[-1,2,1,-4] 1
输出结果
2