इस समस्या में, हमें एक सरणी arr[] दी गई है जिसमें N पूर्णांक अनसॉर्टेड क्रम में संग्रहीत हैं। हमारा कार्य दिए गए योग वाला एक सबएरे ढूंढना है।
उदाहरण से समझते हैं:
इनपुट: arr[] = {2, 5, -1, 4, 6, -9, 5} योग = 14 आउटपुट: सबएरे = {5, -1, 4, 6} व्याख्या:
सबएरे योग = 5 - 1 + 4 + 6 = 14
समाधान दृष्टिकोण
समस्या का एक सरल समाधान नेस्टेड लूप का उपयोग करना है। हम सरणी के माध्यम से लूप करेंगे और एक आंतरिक लूप का उपयोग करके सबएरे ढूंढेंगे। प्रत्येक सबएरे के लिए हम सभी तत्वों का योग ज्ञात करेंगे और उसकी तुलना दिए गए योग मान से करेंगे। यदि यह बराबर है, तो सबएरे प्रिंट करें। यदि सरणी के सभी तत्व ट्रैवर्स हो जाते हैं, तो प्रिंट करें कि ऐसा कोई सरणी नहीं मिला।
एल्गोरिथम
चरण 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 = 14; findSubArrayWithSum(arr, n, sum); return 0; } आउटपुट
Subarray with given sum : { 5 -1 4 6 } समस्या को हल करने का एक बेहतर दृष्टिकोण हैशमैप का उपयोग करना है। हैशमैप वर्तमान इंडेक्स तक का प्रीफिक्स योग संग्रहीत करेगा। और किसी भी इंडेक्स के लिए, जांचें कि क्या दिए गए योग वाला सबएरे मौजूद है। हम जांचेंगे कि क्या कोई प्रीफिक्स है जिसका योग = योग - मान है।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include <bits/stdc++.h> using namespace std; void printSubArray(int arr[], int i, int j){ cout<<"{ "; for(; i <= j; i++) cout<<arr[i]<<" "; cout<<"}"; } void findSubArrayWithSum(int arr[], int n, int sum) { unordered_map<int, int> map; int curr_sum = 0; for (int i = 0; i < n; i++){ curr_sum = curr_sum + arr[i]; if (curr_sum == sum) { cout<<"SubArray with the given sum :"; printSubArray(arr, 0, i); return; } if (map.find(curr_sum - sum) != map.end()) { cout<<"SubArray with the given sum : "; printSubArray(arr, map[curr_sum - sum] + 1 , i); return; } map[curr_sum] = i; } cout<<"No subarray found!"; } int main() { int arr[] = { 2, 5, -1, 4, 6, 9, 3}; int n = sizeof(arr) / sizeof(arr[0]); int sum = 14; findSubArrayWithSum(arr, n, sum); return 0; } आउटपुट
SubArray with the given sum : { 5 -1 4 6 }