کلنجار رفتن با چالش‌های کدنویسی از روش‌های خیلی خوب برای یادگیری بهتر و تثبیت مفاهیم برنامه‌نویسی و تلنگر زدن به ذهنیه که تنبل شده. فرقی هم نداره توسعه‌دهندۀ حرفه‌ای باشید یا تازه‌کار و برای همینه که چالش‌ها سطح‌های آسون تا سخت دارن. منم از این کار خوشم می‌آد و گهگاه سراغ این‌جور چالش‌ها می‌رم. اما یک نقل معروف هست که می‌گه:
تا وقتی نتونی موضوعی رو به شخص دیگه‌ای آموزش بدی، واقعاً اون رو یاد نگرفتی.
برای همین تصمیم گرفتم جواب چالش‌هایی رو که حل می‌کنم، با کمی توضیحات، اینجا بذارم؛ اول از همه برای اینکه خودم بهتر یاد بگیرم و بعد برای اینکه شاید به درد شخص دیگه‌ای هم بخوره.
خب بریم سراغ سوال.
سوال: عدد s و آرایه‌ای نامرتب از اعداد طبیعی به شما داده شده است. زیرآرایه‌ای از این آرایه را پیدا کنید که جمع اعضای آن برابر با s باشد. اندیس (Index) چپ‌ترین و راست‌ترین عضو زیرآرایه را برگردانید.
مثال:
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
سطح: متوسط
منبع:
توی اطلاعات داده‌شده دوتا موضوع اهمیت کلیدی دارن. یکی اینکه اعضای زیرآرایۀ ما طبیعی‌ان (در نتیجه منفی نیستن) و دوم اینکه آرایۀ ما نامرتبه (که اگر مرتب بود حلش خیلی ساده می‌شد).
بیایم توی گام اول سعی کنیم ساده‌ترین راهی رو پیاده کنیم که به ذهنمون می‌رسه و اون چیه؟ بررسی یک به یک تمام زیرآرایه‌ها و مقایسه‌شون با عدد 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).
حالا اگر اعضای آرایه از اعداد صحیح بودن چی می‌شد؟ یعنی اگر بینشون اعداد منفی هم بود، آیا این راه حل جواب می‌داد؟ مطمئناً نه. اما اون سوال دیگه‌ایه که یه زمان دیگه راه حلش رو بررسی می‌کنیم.
