हमें नंबर्स का एक ऐरे और एक नंबर दिया गया है; हमारा काम एक फ़ंक्शन लिखना है जो उन सभी सब ऐरे का एक ऐरे लौटाता है जो दूसरे आर्गुमेंट के रूप में प्रदान किए गए नंबर तक जुड़ते हैं।
उदाहरण के लिए:
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 ] ]
