پیدا کردن جفت اعداد با مجموع مشخص در آرایه: از روش ساده تا بهینه

امروز تو یکی از مصاحبه‌های کاریم به یه چالش جالب برخوردم که دوست داشتم باهاتون در میون بذارمش. مسئله این بود که: "چطوری می‌تونیم ایندکس دوتا عدد تو یه آرایه رو پیدا کنیم که مجموعشون برابر با یه عدد خاص بشه؟"

فرض کن یه آرایه داریم مثل این:

const data = [1, 2, 3, 4, 5, 6, 7, 8, 9];

حالا می‌خوایم ایندکس دوتا عددی که جمعشون ۱۰ می‌شه رو پیدا کنیم.

روش اول: استفاده از دو حلقه تو در تو

یه روش ساده اینه که از دو تا حلقه استفاده کنیم و همه جفت‌ عددهای ممکن رو چک کنیم. اینجوری می‌تونیم ببینیم که آیا جمعشون ۱۰ می‌شه یا نه:

const pairs = [];

for (let i = 0; i < data.length; i++) {
    for (let j = i + 1; j < data.length; j++) {
        if (data[i] + data[j] === 10) pairs.push([i, j]);
    }
}

console.log(pairs);

این کد درسته و جفت‌هایی که مجموعشون ۱۰ می‌شه رو پیدا می‌کنه. ولی مشکلی که داره اینه که از دو تا حلقه تو در تو استفاده می‌کنه، و پیچیدگی زمانی‌اش O(n²) می‌شه، که برای آرایه‌های بزرگ زیاد بهینه نیست.

روش بهینه تر: استفاده از یک حلقه و دیکشنری

برای اینکه روش رو بهینه‌تر کنیم، می‌تونیم از یه دیکشنری استفاده کنیم و مسأله رو با یه حلقه حل کنیم. این روش پیچیدگی زمانی رو به O(n) کاهش می‌ده:

const indexMap = {};
const pairs = [];

for (let i = 0; i < data.length; i++) {
    const complement = 10 - data[i];

    if (indexMap.hasOwnProperty(complement)){
        pairs.push([indexMap[complement], i]);
    }

    indexMap[data[i]] = i;
}

console.log(pairs);

اینجا، برای هر عدد، مکملش (یعنی عددی که باهاش جمع بشه و ۱۰ بده) رو حساب می‌کنیم. بعد چک می‌کنیم که آیا قبلاً این مکمل توی دیکشنری بوده یا نه. اگه بوده یعنی قبلاً یه عدد داشتیم که با عدد فعلی جمعش ۱۰ می‌شه و ایندکس اون دوتا رو ذخیره می‌کنیم. این روش خیلی سریع‌تر و بهینه‌تره.

امیدوارم براتون مفید بوده باشه 🫰❤️