আমাদের কাজ হলো টু-সম সমস্যাটি সর্বোচ্চ লিনিয়ার টাইমে সমাধান করা।
Two Sum Problem (দুই সংখ্যার যোগফল সমস্যা)
একটি ইন্টিজারের অ্যারে দেওয়া থাকলে, আমাদের দুটি এমন নাম্বার খুঁজে বের করতে হবে যেগুলোর যোগফল একটি নির্দিষ্ট টার্গেট নাম্বারের সমান হবে।
twoSum ফাংশনটি সেই দুটি নাম্বারের ইনডেক্স রিটার্ন করবে যেগুলোর যোগফল টার্গেটের সমান, এবং যদি কোনো দুটি এলিমেন্ট যোগ করলে টার্গেট হয় না, তবে খালি অ্যারে রিটার্ন করবে।
O(n) টাইমে সমাধান
আমরা একটি হ্যাশম্যাপ ব্যবহার করব যেটি ইতিমধ্যে এসেছে এলিমেন্টগুলোর রেকর্ড রাখবে। প্রতিটি পাসে আমরা চেক করব যে ম্যাপে কি এমন কোনো এলিমেন্ট আছে যা করেন্ট এলিমেন্টের সাথে যোগ করলে টার্গেট হয়, যদি থাকে তবে তাদের ইনডেক্স ধরে অ্যারে রিটার্ন করব এবং যদি পুরো লুপ পার করে যাই tanpa এই কন্ডিশন স্যাটিসফাই না করলে খালি অ্যারে রিটার্ন করব।
উদাহরণ
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 ] []
