আমাদের একটি ফাংশন লিখতে হবে, বলুন threeSum() যেটি সংখ্যার অ্যারে এবং একটি টার্গেটসাম নেয়। এটা পরীক্ষা করে যে অ্যারেতে কোনো তিনটি সংখ্যা আছে কি না যা লক্ষ্য যোগফল যোগ করে, যদি অ্যারেতে এই ধরনের তিনটি সংখ্যা থাকে, তাহলে এটি তাদের সূচকগুলি অ্যারেতে ফিরিয়ে দেবে অন্যথায় এটি -1 ফেরত দেবে।
পন্থা
পদ্ধতিটি সহজ, আমরা প্রথমে একটি ফাংশন twoSum() লিখব, যা একটি অ্যারে এবং অ্যাটার্গেট যোগফল নেয় এবং দুটি সংখ্যার সূচকগুলি ফেরত দিতে রৈখিক সময় এবং স্থান নেয় যা অন্যথায় -1 যোগ করে।
তারপরে আমরা প্রকৃত ফাংশন threeSum() লিখি, যেটি তৃতীয় উপাদানের সূচী খুঁজে বের করতে অ্যারের প্রতিটি উপাদানের উপর পুনরাবৃত্তি করে যা twoSum() সংখ্যার সাথে যোগ করা হলে প্রকৃত লক্ষ্য পর্যন্ত যোগ হতে পারে।
অতএব, এভাবে আমরা O(N^2) সময়ে তিনটি উপাদান খুঁজে পেতে পারি। এর জন্য কোড লিখি -
উদাহরণ
const arr = [1,2,3,4,5,6,7,8];
const twoSum = (arr, sum) => {
const map = {};
for(let i = 0; i < arr.length; i++){
if(map[sum-arr[i]]){
return [map[sum-arr[i]], i];
};
map[arr[i]] = i;
};
return -1;
};
const threeSum = (arr, sum) => {
for(let i = 0; i < arr.length; i++){
const indices = twoSum(arr, sum-arr[i]);
if(indices !== -1 && !indices.includes(i)){
return [i, ...indices];
};
};
return -1;
};
console.log(threeSum(arr, 9));
console.log(threeSum(arr, 8));
console.log(threeSum(arr, 13));
console.log(threeSum(arr, 23)); আউটপুট
কনসোলে আউটপুট হবে −
[ 0, 2, 4 ] [ 0, 2, 3 ] [ 0, 4, 6 ] -1
