संख्या के बराबर योग के साथ सभी उप-सरणी खोजें? जावास्क्रिप्ट (स्लाइडिंग विंडो एल्गोरिथम)

हमें संख्याओं की एक सरणी और एक संख्या दी गई है; हमारा काम एक ऐसा फ़ंक्शन लिखना है जो सभी उप सरणियों की एक सरणी देता है जो दूसरे तर्क के रूप में प्रदान की गई संख्या को जोड़ता है।

उदाहरण के लिए -

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));

प्रारंभ और अंत चर अलग-अलग बिंदुओं पर विंडो की प्रारंभिक और समाप्ति स्थिति को दर्शाते हैं।

प्रारंभ में दोनों 0 से शुरू हुए, फिर हमने विंडो के आकार में वृद्धि की, यदि आवश्यक योग दिए गए योग से कम था, तो विंडो का आकार घटाया यदि यह अधिक था और यदि किसी भी बिंदु पर दोनों का योग होता है, तो हमने उस सबएरे को आवश्यक सरणी में धकेल दिया। और खिड़की को इकाई दूरी से दाईं ओर ले जाया गया।

आउटपुट

कंसोल में इस कोड का आउटपुट होगा -

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]