इस समस्या में, हमें पूर्णांक मानों की एक सरणी दी गई है और हमें इस सरणी से उन सभी उपसरणी को प्रिंट करना है जिनका योग 0 के बराबर है।
विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं,
इनपुट: सरणी = [-5, 0, 2, 3, -3, 4, -1] आउटपुट: इंडेक्स 1 से 4 तक उपसरणी का योग 0 है। इंडेक्स 5 से 7 तक उपसरणी का योग 0 है। इंडेक्स 0 से 7 तक उपसरणी का योग 0 है।
इस समस्या को हल करने के लिए, हम सभी संभावित उपसरणी की जांच करेंगे। और जांचेंगे कि क्या इन उपसरणी का योग 0 के बराबर है और उन्हें प्रिंट करेंगे। यह समाधान समझने में आसान है लेकिन समाधान जटिल है, और इसकी समय जटिलता O(n^2) क्रम की है।
इस समस्या का एक बेहतर समाधान हैशिंग का उपयोग करना है। इसे हल करने के लिए हम योग ढूंढेंगे यदि यह 0 के बराबर है तो इसे हैश टेबल में जोड़ देंगे।
एल्गोरिदम
चरण 1: एक योग वेरिएबल बनाएं। चरण 2: यदि योग = 0, तो उपसरणी सरणी के इंडेक्स 0 से अंतिम इंडेक्स तक शुरू होती है। चरण 3: यदि वर्तमान योग हैश टेबल में है। चरण 4: यदि योग मौजूद है, तो i+1 से n तक की उपसरणी शून्य होनी चाहिए। चरण 5: अन्यथा हैश टेबल में डालें।
उदाहरण
#include <bits/stdc++.h> using namespace std; vector< pair<int, int> > findSubArrayWithSumZero(int arr[], int n){ unordered_map<int, vector<int> >map; vector <pair<int, int>> out; int sum = 0; for (int i = 0; i < n; i++){ sum += arr[i]; if (sum == 0) out.push_back(make_pair(0, i)); if (map.find(sum) != map.end()){ vector<int> vc = map[sum]; for (auto it = vc.begin(); it != vc.end(); it++) out.push_back(make_pair(*it + 1, i)); } map[sum].push_back(i); } return out; } int main(){ int arr[] = {-5, 0, 2, 3, -3, 4, -1}; int n = sizeof(arr)/sizeof(arr[0]); vector<pair<int, int> > out = findSubArrayWithSumZero(arr, n); if (out.size() == 0) cout << "No subarray exists"; else for (auto it = out.begin(); it != out.end(); it++) cout<<"Subarray with sum 0 is from "<<it->first <<" to "<<it->second<<endl; return 0; } आउटपुट
Subarray with sum 0 is from 1 to 1 Subarray with sum 0 is from 0 to 3 Subarray with sum 0 is from 3 to 4 Subarray with sum 0 is from 0 to 6 Subarray with sum 0 is from 4 to 6
