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