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