दिए गए योग के साथ उपसरणी खोजें - (नकारात्मक संख्याओं को संभालता है) C++ . में

इस समस्या में, हमें अक्रमित क्रम में संग्रहीत N पूर्णांकों से युक्त एक सरणी arr[] दी गई है। हमारा काम है दी गई राशि के साथ एक उप-सरणी ढूंढना ।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

Input : arr[] = {2, 5, -1, 4, 6, -9, 5} sum = 14
Output : subarray = {5, -1, 4, 6}

स्पष्टीकरण -

Subarray sum = 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 }