3Sum Closest trong C ++

Giả sử chúng ta có một dãy số với n số nguyên và một mục tiêu. Chúng ta phải tìm ba số nguyên trong số sao cho tổng gần nhất với mục tiêu. Chúng tôi sẽ trả về tổng của ba số nguyên. Chúng ta có thể có một giả định rằng mỗi đầu vào sẽ có chính xác một giải pháp. Vì vậy, nếu mảng đã cho giống như [-1,2,1, -4] và đích là 1, thì bộ ba sẽ là [-1,2,1] cái này có tổng gần nhất, đó là 2.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• Sắp xếp mảng nums, ans:=0, diff:=Infinity, n:=kích thước của nums
• cho tôi trong phạm vi từ 0 đến n - 1
  • left:=i + 1, right:=n - 1
  • trong khi bên trái
  • temp:=nums [left] + nums [right] + nums [i]
  • if | target - temp |
  • nếu temp =target thì trả về nhiệt độ, ngược lại khi temp> target thì giảm sang phải 1, ngược lại tăng sang trái 1

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

[-1,2,1,-4]
1

Đầu ra

2