حل چالش‌های کدنویسی با گولنگ - زیرآرایه‌ای با مجموع مشخص

کلنجار رفتن با چالش‌های کدنویسی از روش‌های خیلی خوب برای یادگیری بهتر و تثبیت مفاهیم برنامه‌نویسی و تلنگر زدن به ذهنیه که تنبل شده. فرقی هم نداره توسعه‌دهندۀ حرفه‌ای باشید یا تازه‌کار و برای همینه که چالش‌ها سطح‌های آسون تا سخت دارن. منم از این کار خوشم می‌آد و گهگاه سراغ این‌جور چالش‌ها می‌رم. اما یک نقل معروف هست که می‌گه:

تا وقتی نتونی موضوعی رو به شخص دیگه‌ای آموزش بدی، واقعاً اون رو یاد نگرفتی.

برای همین تصمیم گرفتم جواب چالش‌هایی رو که حل می‌کنم، با کمی توضیحات، اینجا بذارم؛ اول از همه برای اینکه خودم بهتر یاد بگیرم و بعد برای اینکه شاید به درد شخص دیگه‌ای هم بخوره.

• راه حل‌ها با زبان گو (Go) پیاده‌سازی می‌شن، اما اگر شما با زبان دیگه‌ای کار می‌کنید، راحت می‌تونید اون‌ها رو با زبان تخصصی خودتون پیاده کنید.

خب بریم سراغ سوال.

سوال: عدد s و آرایه‌ای نامرتب از اعداد طبیعی به شما داده شده است. زیرآرایه‌ای از این آرایه را پیدا کنید که جمع اعضای آن برابر با s باشد. اندیس (Index) چپ‌ترین و راست‌ترین عضو زیرآرایه را برگردانید.

• منظور از زیرآرایه، آرایه‌ای شامل چند عضو پشت سر هم از آرایۀ اصلی است.
• اندیس‌ها باید بر مبنای سیستم شماره‌گذاری از 1 برگردانده شوند.
• اگر چند زیرآرایه شرایط جواب را احراز می‌کرد، آنی را برگردانید که از چپ به راست، زودتر شروع می‌شود.
• اگر چنین زیرآرایه‌ای وجود نداشت 1- را برگردانید.

مثال:

Example 1:
Input: arr[] = [1,2,3,7,5], s = 12
Output: 2 4

Example 2:
Input: arr[] = [1,2,3,4,5,6,7,8,9,10], s = 15,
Output: 1 5

Example 3:
Input: arr[] = [5,3,4], s = 2
Output: -1 -1

سطح: متوسط

منبع:

• GeekforGeeks - Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, …

ساده‌ترین پاسخ

توی اطلاعات داده‌شده دوتا موضوع اهمیت کلیدی دارن. یکی اینکه اعضای زیرآرایۀ ما طبیعی‌ان (در نتیجه منفی نیستن) و دوم اینکه آرایۀ ما نامرتبه (که اگر مرتب بود حلش خیلی ساده می‌شد).

بیایم توی گام اول سعی کنیم ساده‌ترین راهی رو پیاده کنیم که به ذهنمون می‌رسه و اون چیه؟ بررسی یک به یک تمام زیرآرایه‌ها و مقایسه‌شون با عدد s. برای این کار کافیه دوتا حلقۀ تودرتو بنویسیم. شمارشگر حلقۀ بیرونی از i شروع می‌شه و حلقۀ درونی تمام زیرآرایه‌ها از i به بعد رو بررسی می‌کنه تا به جواب برسه.

این راه جواب می‌ده، اما بهینه نیست؛ چون از حلقه‌های تودرتو استفاده کردیم، پیچیدگی زمانی O(N^2) داره، هرچند پیچیدگی حافظه‌ایش O(1) است.

پاسخ بهینه

چطور می‌تونیم از پیچیدگی زمانی این راه کم کنیم؟ می‌تونیم از این توضیح صورت سوال استفاده کنیم: اعداد درون آرایه طبیعی‌ان. در نتیجه هیچ عدد منفی بین این اعداد نیست. این نکته چه کمکی به ما می‌کنه؟

فرض کنید ما از اولین عضو آرایه شروع می‌کنیم و مدام اعضای بعدی رو به زیرآرایه‌مون اضافه می‌کنیم تا ببینیم به جواب می‌رسیم یا نه. توی نقطه‌ای، به زیرآرایه‌ای می‌رسیم که از 0 شروع می‌شه و به j ختم می‌شه و جمع اعدادش از s بزرگ‌تره. چون همۀ اعداد درون آرایه غیرمنفی‌ان، امکان نداره که با جلوتر رفتن از j و بزرگ‌تر کردن زیرآرایه، به s برسیم. حالا که نمی‌تونیم با حفظ این شرایط جلوتر بریم، کافیه اولین عضو زیر آرایه (یعنی 0) رو از زیرآرایه پرت کنیم بیرون. در نتیجه حالا زیرآرایه‌ای از 1 تا j داریم. اینجا دوباره بررسی می‌کنیم که آیا این زیرآرایه جواب سوال ما هست یا نه. اگر نبود و جمع اعدادش از s کوچک‌تر بود، باز به j اضافه می‌کنیم و اگر همچنان از s بزرگ‌تر بود، یک عضو دیگه رو از ابتدای زیرآرایه بیرون می‌اندازیم. همین روند رو اون‌قدر ادامه می‌دیم که j به آخرین عضو آرایۀ اصلی برسه. اگر j به آخرین عضو آرایۀ اصلی رسید و ما همچنان به جواب نرسیده بودیم، مشخص می‌شه که آرایۀ داده‌شده هیچ زیرآرایه‌ای با مجموع اعداد s نداره. به همین سادگی!

کدش در زبان گو اینجوری می‌شه:

پیچیدگی زمانی این راه حل O(N) است، چون در بدترین حالت از ابتدا تا انتهای آرایه رو پیمایش کردیم و پیچدگی حافظه‌ایش هم O(1).

چندتا نکته دربارۀ راه حل بالا:

• اول دوتا حالت خاص رو بررسی کردیم، یکی اینکه ورودی، آرایۀ خالی باشه و دیگری اینکه آرایه یک عضو داشته باشه و اون عضو برابر s باشه.
• توی خط 13 موقعیت شروع و پایان زیرآرایه رو با یک جمع کردیم، چون توی زبان گو اندیس اعضای آرایه‌ها از صفر شمرده می‌شه، اما صورت سوال از ما خواسته که بر اساس سیستم شماره‌گذاری از 1 جواب رو اعلام کنیم.
• اگر با Go آشنایی ندارید، شاید براتون جالب باشه که بدونید در گو برای پیاده‌سازی حلقۀ While، از for استفاده می‌کنیم، به همین صورتی که مشاهده می‌کنید.

حالا اگر اعضای آرایه از اعداد صحیح بودن چی می‌شد؟ یعنی اگر بینشون اعداد منفی هم بود، آیا این راه حل جواب می‌داد؟ مطمئناً نه. اما اون سوال دیگه‌ایه که یه زمان دیگه راه حلش رو بررسی می‌کنیم.