हमारा काम एक ऐसा फ़ंक्शन लिखना है जो दो-योग की समस्या को सबसे अधिक रैखिक समय में हल करता है।
दो सम समस्या
पूर्णांकों की एक सरणी को देखते हुए, हमें दो संख्याएँ इस प्रकार ढूंढनी होंगी कि वे एक विशिष्ट लक्ष्य संख्या में जुड़ जाएँ।
फ़ंक्शन टूसम को उन दो संख्याओं के सूचकांक लौटाना चाहिए जो लक्ष्य में जुड़ते हैं, और यदि कोई दो तत्व लक्ष्य में नहीं जुड़ते हैं, तो हमारे फ़ंक्शन को एक खाली सरणी वापस करनी चाहिए।
समस्या को O(n) समय में हल करना
हम पहले से दिखाई देने वाली वस्तुओं का रिकॉर्ड रखने के लिए हैशमैप का उपयोग करेंगे, प्रत्येक पास पर हम जांच करेंगे कि क्या मानचित्र में कोई तत्व मौजूद है, जो वर्तमान तत्व में जोड़ा जाता है, यदि कोई है तो हम एक सरणी वापस कर देंगे जिसमें उनके सूचकांक और अगर हम इस शर्त को पूरा किए बिना पूरे लूप से गुजरते हैं, तो हम एक खाली सरणी वापस कर देंगे।
उदाहरण
const arr = [2, 5, 7, 8, 1, 3, 6, 9, 4];
const sum = 10;
const twoSum = (arr, sum) => {
const map = {};
for(let i = 0; i < arr.length; i++){
const el = sum - arr[i];
if(map[el]){
return [map[el], i];
};
map[arr[i]] = i;
};
return [];
};
console.log(twoSum(arr, sum));
console.log(twoSum(arr, 12));
console.log(twoSum(arr, 13));
console.log(twoSum(arr, 14));
console.log(twoSum(arr, 24)); आउटपुट
कंसोल में आउटपुट होगा -
[ 2, 5 ] [ 1, 2 ] [ 1, 3 ] [ 3, 6 ] []