इस समस्या में, हमें एक सरणी arr[] दी गई है जिसमें N धनात्मक पूर्णांक अनसॉर्टेड क्रम में संग्रहीत हैं। हमारा कार्य दिए गए योग वाला एक सबएरे ढूंढना है।
उदाहरण से समझते हैं:
इनपुट: arr[] = {2, 5, 1, 4, 6, 9, 5} योग = 11 आउटपुट: सबएरे = {1, 4, 6} व्याख्या:
सबएरे योग = 1 + 4 + 6 = 11
समाधान दृष्टिकोण
समस्या का एक सरल समाधान नेस्टेड लूप का उपयोग करना है। हम सरणी के माध्यम से लूप करेंगे और एक आंतरिक लूप का उपयोग करके सबएरे ढूंढेंगे। प्रत्येक सबएरे के लिए हम सभी तत्वों का योग ज्ञात करेंगे और उसकी तुलना दिए गए योग मान से करेंगे। यदि यह बराबर है, तो सबएरे प्रिंट करें। यदि सरणी के सभी तत्व ट्रैवर्स हो जाते हैं, तो प्रिंट करें कि ऐसा कोई सरणी नहीं मिला।
एल्गोरिथम
चरण 1 - सरणी के माध्यम से लूप करें, i → 0 से (n-1) तक।
चरण 1.1 - प्रत्येक तत्व के लिए, सभी संभावित सबएरे के लिए प्रत्येक सबएरे का योग ज्ञात करें।
चरण 1.2 - यदि वर्तमान सबएरे तत्वों का योग दिए गए सबएरे के बराबर है, तो सबएरे प्रिंट करें।
चरण 2 - यदि सरणी के सभी तत्व ट्रैवर्स हो जाते हैं और कोई सबएरे नहीं मिलता है। प्रिंट करें "दिए गए योग वाला कोई सबएरे नहीं मिला!"।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include <bits/stdc++.h> using namespace std; void printSubArray(int arr[], int i, int j){ cout<<"{"; for(; i < j; i++) cout<<arr[i]<<" "; cout<<"}"; } int findSubArrayWithSum(int arr[], int n, int sum) { int currSum; for (int i = 0; i < n; i++) { currSum = arr[i]; for (int j = i + 1; j <= n; j++) { if (currSum == sum) { cout<<"Subarray with given sum : "; printSumArray(arr, i, j); return 1; } if (currSum > sum || j == n) break; currSum = currSum + arr[j]; } } cout<<"No subarray found"; return 0; } int main() { int arr[] = { 2, 5, 1, 4, 6, 9, 3}; int n = sizeof(arr) / sizeof(arr[0]); int sum = 11; findSubArrayWithSum(arr, n, sum); return 0; } आउटपुट
Subarray with given sum : { 1 4 6 } समस्या को हल करने का एक बेहतर दृष्टिकोण स्लाइडिंग विंडो के समान एक विधि का उपयोग करना है लेकिन यहां हमारे पास एक वेरिएबल विंडो होगी। हम सरणी के पहले तत्व से शुरू करेंगे, विंडो में तत्वों को तब तक जोड़ेंगे जब तक योग दिए गए योग से अधिक न हो जाए। यदि यह अधिक हो जाता है तो तत्वों को तब तक हटाएं जब तक यह फिर से योग से कम न हो जाए। यह प्रक्रिया तब तक करें जब तक पूरी सरणी ट्रैवर्स न हो जाए।
यदि किसी बिंदु पर, विंडो योग दिए गए योग के बराबर हो जाता है, तो सबएरे प्रिंट करें। और यदि कोई विंडो नहीं मिलती जिसका योग दिए गए योग के बराबर हो और ट्रैवर्स करने के लिए कोई तत्व न हो, तो प्रिंट करें "कोई सबएरे नहीं मिला!"।
एल्गोरिथम
आरंभीकरण - windowSum = 0, sindex = 0, endindex = 0
चरण 1 - endIndex का उपयोग करके सरणी को ट्रैवर्स करें।
चरण 1.1 - windowSum को तत्वों को जोड़कर अपडेट करें जब तक windowSum दिए गए योग से अधिक न हो जाए, यानी यदि (windowSum < योग) -> windowSum = windowSum + arr[endIndex]।
चरण 1.2 - यदि windowSum योग से अधिक है, तो तत्वों को हटाकर विंडो का आकार कम करें, यानी जबकि (windowSum < योग) -> windowSum = windowSum - arr[endIndex]।
चरण 1.3 - यदि windowSum == योग, तो सबएरे प्रिंट करें।
चरण 2 - यदि सरणी ट्रैवर्स हो जाती है, तो प्रिंट करें -> 'संभव नहीं'।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include <bits/stdc++.h> using namespace std; void printSubArray(int arr[], int i, int j){ cout<<"{ "; for(; i < j; i++) cout<<arr[i]<<" "; cout<<"}"; } int findSubArrayWithSum(int arr[], int n, int sum) { int windowSum = arr[0], startIndex = 0, endIndex; for (endIndex = 1; endIndex <= n; endIndex++) { while (windowSum > sum && startIndex < endIndex - 1) { windowSum -= arr[startIndex]; startIndex++; } if (windowSum == sum) { cout << "Subarray with given sum : "; printSumArray(arr, startIndex ,endIndex); return 1; } if (endIndex < n) windowSum += arr[endIndex]; } cout << "No subarray found"; return 0; } int main() { int arr[] = { 2, 5, 1, 4, 6, 9, 3}; int n = sizeof(arr) / sizeof(arr[0]); int sum = 11; findSubArrayWithSum(arr, n, sum); return 0; } आउटपुट
Subarray with given sum : { 1 4 6 } 