JavaScript-এ অ্যারেতে তিনটি সংখ্যার যোগফল টার্গেটের সমান খুঁজে বের করা (3Sum)

ভূমিকা

ক্লাসিক **3Sum Problem**: একটি অ্যারে এবং টার্গেট সম দেওয়া থাকলে, অ্যারেতে তিনটি সংখ্যা আছে কিনা যাদের যোগফল টার্গেটের সমান। আছে তবে তাদের ইন্ডেক্স রিটার্ন করুন, নাইলে -1।

সম্পূর্ণ কোড (Two Sum + Loop)

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));  // [0, 2, 4] → 1+3+5=9
console.log(threeSum(arr, 8));  // [0, 2, 3] → 1+3+4=8
console.log(threeSum(arr, 13)); // [0, 4, 6] → 1+5+7=13
console.log(threeSum(arr, 23)); // -1

আউটপুট

[0, 2, 4]
[0, 2, 3]
[0, 4, 6]
-1

অ্যালগরিদম বিশ্লেষণ

• Two Sum: Hash Map ব্যবহার করে O(n)
• Three Sum: প্রতিটি এলিমেন্টের জন্য Two Sum কল → O(n²)
• স্পেস: O(n) - Hash Map এর জন্য

⚠️ মূল কোডের সমস্যা

`twoSum` পুরো অ্যারেতে খুঁজে, বর্তমান `i` ইন্ডেক্স বাদ দেওয়া হয় না। `!indices.includes(i)` চেক আছে, কিন্তু যদি `twoSum` বর্তমান `i` ব্যবহার করে থাকে তবে সমস্যা হয়।

সংশোধিত ও অপ্টিমাইজড ভার্সন

১. সঠিক Two Sum (বadier índex বাদ)

const twoSum = (arr, target, excludeIdx = -1) => {
  const map = new Map();
  for (let i = 0; i < arr.length; i++) {
    if (i === excludeIdx) continue;
    const complement = target - arr[i];
    if (map.has(complement)) return [map.get(complement), i];
    map.set(arr[i], i);
  }
  return -1;
};

const threeSum = (arr, target) => {
  for (let i = 0; i < arr.length; i++) {
    const indices = twoSum(arr, target - arr[i], i);
    if (indices !== -1) return [i, ...indices];
  }
  return -1;
};

২. Sort + Two Pointer (O(n²) - স্ট্যান্ডার্ড 3Sum)

const threeSumSorted = (arr, target) => {
  const indexed = arr.map((val, idx) => ({ val, idx })).sort((a,b) => a.val - b.val);
  const n = indexed.length;
  
  for (let i = 0; i < n - 2; i++) {
    let left = i + 1, right = n - 1;
    while (left < right) {
      const sum = indexed[i].val + indexed[left].val + indexed[right].val;
      if (sum === target) {
        return [indexed[i].idx, indexed[left].idx, indexed[right].idx];
      } else if (sum < target) left++;
      else right--;
    }
  }
  return -1;
};

৩. সব সম্ভাব্য ট্রিপলেট বের করা (All Triplets)

const allThreeSum = (arr, target) => {
  const result = [];
  const indexed = arr.map((val, idx) => ({ val, idx })).sort((a,b) => a.val - b.val);
  
  for (let i = 0; i < indexed.length - 2; i++) {
    if (i > 0 && indexed[i].val === indexed[i-1].val) continue; // ডুপ্লিকেট স্কিপ
    let left = i + 1, right = indexed.length - 1;
    while (left < right) {
      const sum = indexed[i].val + indexed[left].val + indexed[right].val;
      if (sum === target) {
        result.push([indexed[i].idx, indexed[left].idx, indexed[right].idx]);
        left++; right--;
        while (left < right && indexed[left].val === indexed[left-1].val) left++;
        while (left < right && indexed[right].val === indexed[right+1].val) right--;
      } else if (sum < target) left++;
      else right--;
    }
  }
  return result.length ? result : -1;
};

ব্যবহারিক অ্যাপ্লিকেশন

• ফিনান্স: ট্রানজেকশন রিকন্সিলিয়েশন
• ক্রিপ্টোগ্রাফি: সাবসেট সম সমস্যা
• গেমিং: রিসোর্স ম্যানেজমেন্ট, ক্রাফটিং রেসিপি
• বায়োইনফরম্যাটিক্স: প্রোটিন মাস স্পেকট্রোমেট্রি

সারাংশ

3Sum সমস্যা O(n²) টাইমে সমাধানযোগ্য। Hash Map পদ্ধতি সহজ কিন্তু সঠিক ইন্ডেক্স এক্সক্লুশন দরকার। Sort + Two Pointer পদ্ধতিটি সবচেয়ে রোবাস্ট এবং সব ট্রিপলেট বের করতে উপযোগী।