मान लीजिए हमारे पास n पूर्णांकों वाली एक सरणी nums और एक लक्ष्य है। हमें nums में तीन पूर्णांक ढूंढने हैं जिनका योग लक्ष्य के सबसे करीब हो। हम तीन पूर्णांकों का योग लौटाएंगे। हम यह मान ले सकते हैं कि प्रत्येक इनपुट का ठीक एक समाधान होगा। तो यदि दी गई सरणी [-1,2,1,-4] जैसी है और लक्ष्य 1 है, तो ट्रिपलेट [-1,2,1] होगा जिसका सबसे करीबी योग 2 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- सरणी nums को सॉर्ट करें, ans := 0, diff := Infinity, n := nums का आकार
- i को 0 से n - 1 तक की रेंज में
- left := i + 1, right := n - 1
- जब तक left < right
- temp := nums[left] + nums[right] + nums[i]
- यदि |लक्ष्य - temp| < diff, तो ans := temp और diff := |लक्ष्य - temp|
- यदि temp = लक्ष्य, तो temp लौटाएं, अन्यथा जब temp > लक्ष्य, तो right को 1 से घटाएं, अन्यथा left को 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