हमें संख्याओं का एक ऐरे और एक संख्या दी गई है; हमारा काम एक फ़ंक्शन लिखना है जो उन सभी सब ऐरे का एक ऐरे लौटाता है जो दूसरे आर्गुमेंट के रूप में प्रदान की गई संख्या तक जुड़ते हैं।
उदाहरण के लिए -
const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27]; const sum = 40; console.log(requiredSum(arr, sum));
निम्नलिखित ऐरे आउटपुट करना चाहिए -
[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]
क्योंकि इन 3 सब ऐरे में से प्रत्येक 40 तक जुड़ता है।
स्लाइडिंग विंडो एल्गोरिदम (रैखिक समय)
यह एल्गोरिदम ज्यादातर तब उपयोग किया जाता है जब हमें एक ऐरे के भीतर सबअरे / स्ट्रिंग के भीतर सबस्ट्रिंग ढूंढना होता है जो कुछ मानदंडों को पूरा करते हैं। और यह समस्या स्लाइडिंग विंडो एल्गोरिदम के लिए एक आदर्श उम्मीदवार है।
स्लाइडिंग विंडो एल्गोरिदम वही है जो इसके नाम से पता चलता है, हम एक विंडो बनाते हैं जो मूल ऐरे का एक सबअरे के अलावा कुछ नहीं है। यह विंडो बढ़ने या घटने से स्थिरता हासिल करने की कोशिश करती है।
स्थिरता से हमारा मतलब समस्या में निर्दिष्ट शर्त है (जैसे यहां एक विशिष्ट संख्या तक जोड़ना)। एक बार यह स्थिर हो जाने पर हम विंडो को रिकॉर्ड करते हैं और इसे स्लाइड करना जारी रखते हैं। आमतौर पर, 90% समस्याओं में, हम विंडो को बाएं से शुरू करते हैं और इसे तब तक स्लाइड करते रहते हैं जब तक इसका अंत ऐरे / स्ट्रिंग के अंत तक नहीं पहुंच जाता।
आइए कोड को देखें ताकि हम स्लाइडिंग विंडोज एल्गोरिदम से अधिक परिचित हो सकें।
उदाहरण
const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27]; const sum = 40; const findSub = (arr, sum) => { const required = []; for(let start = 0, end = 0, s = 0; end <= arr.length || s > sum ; ){ if(s < sum){ s += arr[end]; end++; }else if(s > sum){ s -= arr[start]; start++; }else{ required.push(arr.slice(start, end)); s -= arr[start]; s += arr[end]; start++; end++; }; }; return required; }; console.log(findSub(arr, sum));
start और end वेरिएबल्स विभिन्न बिंदुओं पर विंडो की प्रारंभिक और अंतिम स्थितियों को दर्शाते हैं।
प्रारंभ में दोनों 0 से शुरू हुए, फिर हमने विंडो का आकार बढ़ाया यदि आवश्यक योग दिए गए योग से कम था, विंडो का आकार घटाया यदि यह अधिक था और यदि किसी भी बिंदु पर दोनों योग बराबर हुए, तो हमने उस सबअरे को आवश्यक ऐरे में पुश किया। और विंडो को यूनिट दूरी से दाएं की ओर ले जाया।
आउटपुट
कंसोल में इस कोड का आउटपुट होगा -
[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]
