3C++에서 가장 가까운 합계

n개의 정수와 하나의 대상이 있는 배열 num이 있다고 가정합니다. 합이 목표에 가장 가깝도록 num에서 세 개의 정수를 찾아야 합니다. 세 정수의 합을 반환합니다. 우리는 각 입력이 정확히 하나의 솔루션을 가질 것이라는 가정을 할 수 있습니다. 따라서 주어진 배열이 [-1,2,1,-4]이고 대상이 1이면 삼중항은 [-1,2,1]이 됩니다. 이것은 가장 가까운 합, 즉 2를 갖습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열 nums, ans :=0, diff :=Infinity, n :=nums 크기 정렬
• 0 ~ n – 1 범위의 i에 대해
  • 왼쪽 :=i + 1, 오른쪽 :=n – 1
  • 왼쪽 <오른쪽
    • temp :=숫자[왼쪽] + 숫자[오른쪽] + 숫자[i]
    • if |대상 – 임시|
    • temp =target이면 temp를 반환하고, 그렇지 않으면 temp> target이면 오른쪽으로 1 감소, 그렇지 않으면 왼쪽으로 1 증가
• 반환

예(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