सी ++ में 3सम निकटतम

मान लीजिए कि हमारे पास n पूर्णांकों और एक लक्ष्य के साथ एक सरणी संख्या है। हमें अंकों में तीन पूर्णांक इस प्रकार ज्ञात करने हैं कि योग लक्ष्य के सबसे निकट हो। हम तीन पूर्णांकों का योग वापस कर देंगे। हम एक धारणा ले सकते हैं कि प्रत्येक इनपुट का ठीक एक समाधान होगा। तो अगर दी गई सरणी [-1,2,1,-4] की तरह है और लक्ष्य 1 है, तो ट्रिपल [-1,2,1] होगा, इसका निकटतम योग है, यानी 2।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सरणी संख्याओं को क्रमबद्ध करें, उत्तर:=0, अंतर:=अनंत, n:=अंकों का आकार
• मैं के लिए 0 से n - 1 की सीमा में
  • बाएं:=i + 1, दाएं:=n – 1
  • बाएं <दाएं
    • अस्थायी:=अंक [बाएं] + अंक [दाएं] + अंक [i]
    • अगर |लक्ष्य - अस्थायी|
    • यदि अस्थायी =लक्ष्य है, तो अस्थायी लौटाएं, अन्यथा जब अस्थायी> लक्ष्य, फिर 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