सभी योगों को 0 योग के साथ प्रिंट करें


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना स्वतंत्र प्रभार वास्तव में जानकारी एज माइक्रोसॉफ्ट ओयो कमरे
ऐरे हैश

आपको एक पूर्णांक सरणी दी जाती है, आपका कार्य योग के साथ सभी संभावित उप-सरणियों को प्रिंट करना है।

उदाहरण

सभी योगों को 0 योग के साथ प्रिंट करें

arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

कलन विधि

  1. कुछ चर के साथ सरणी तत्वों के योग का पता लगाएं, योग 0 के साथ उप-सरणी का ट्रैक रखने के लिए "सम" कहें।
  2. If राशि 0 पाया जाता है इसका मतलब है कि संभावित उप-सरणी 0 से वर्तमान सूचकांक तक पाई जाती है।
  3. अगर जांच राशि उपरोक्त प्रक्रिया से पाया जाता है, हमारे में मौजूद है नक्शा या नहीं.
  4. यदि मानचित्र में योग है, तो इसका मतलब है कि यह पिछले उप-सरणी का कुल योग था और अब यह वर्तमान सूचकांकों तक तत्व का योग बन जाता है।
  5. यदि यह पहले से मौजूद नहीं था, तो मानचित्र में वर्तमान योग डालें।

व्याख्या

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

हम एक ऐसा नक्शा बनाएंगे जिसमें मूल्य के रूप में अस्थायी राशि और सदिश राशि हो। तो, यहां वेक्टर उन सूचकांकों का प्रतिनिधित्व करता है जिन पर इनपुट की शुरुआत से तत्वों का योग वर्तमान राशि के बराबर है।

इसके बाद, हम एरे पर ट्रेस करना शुरू करते हैं। इसलिए, जैसा कि हम आगे बढ़ते हैं, हम तत्वों को एक चर राशि में जोड़ते रहते हैं। अगर द योग किसी भी क्षण 0 पाया जाता है। तो, इसका मतलब यह है कि शुरू से उप-सरणी 0. है और अगर कुछ सूचकांकों को भी मिला है, जिसमें 0 के बराबर राशि थी।

यदि योग शून्य नहीं पाया जाता है। तब हम जांचते हैं कि क्या मानचित्र में वह राशि है। यदि मानचित्र में गणना योग नहीं है। तब कोई भी सबर्रे मौजूद नहीं होता है जो वर्तमान इंडेक्स पर समाप्त होता है और इसमें 0. होता है। इसलिए, सभी सब-एरेज को खोजने के बाद, जो वर्तमान इंडेक्स पर समाप्त होता है और 0. के बराबर राशि होता है। हम वर्तमान इंडेक्स को वेक्टर में जोड़ देंगे। वह मानचित्र जिसमें कुंजी के रूप में वर्तमान राशि होती है।

लेकिन अगर मानचित्र में यह योग होता है तो इसका मतलब है कि हमें कुछ पिछले उप-सरणियाँ मिलीं जिनका योग समान था। फिर हमें उस राशि और सूचकांकों के मूल्य को जोड़ना होगा।

और इसमें से, हम अपनी सूची वापस करते हैं जिसे हमने एक वेक्टर के रूप में घोषित किया है। अगर वहाँ से वापसी मान का आकार 0 है तो इसका मतलब है कि हमें कुछ और नहीं मिला है।

C ++ कोड सभी योगों को 0 योग के साथ प्रिंट करने के लिए

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;
vector< pair<int, int> > getSubArray(int arr[], int n)
{
  unordered_map<int, vector<int> > Map;
  vector <pair<int, int>> result;
  int sum = 0;
  for (int i = 0; i < n; i++)
  {
    sum += arr[i];
    if (sum == 0)
      result.push_back(make_pair(0, i));
        if (Map.find(sum) != Map.end())
    {
      vector<int> vec = Map[sum];
      for (auto val = vec.begin(); val != vec.end(); val++)
        result.push_back(make_pair(*val + 1, i));
    }
    Map[sum].push_back(i);
  }
  return result;
}
void print(vector<pair<int, int>> result)
{
  for (auto j= result.begin(); j != result.end(); j++)
    cout << "Sub-Array found from " << j->first << " index to " << j->second <<" index"<< endl;
}
int main()
{
    int arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
  vector<pair<int, int> > result = getSubArray(arr, n);
  if (result.size() == 0)
    cout << "No such Sub-array exists";
  else
    print(result);

  return 0;
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

जावा कोड 0 राशि के साथ सभी उप-प्रिंट करने के लिए

import java.util.*;
class Pair
{
    int start, end;
    Pair(int a, int b)
    {
        start = a;
        end = b;
    }
}
class printSubArray0Sum
{
    public static ArrayList<Pair> getSubArray(int[] arr, int n)
    {
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        ArrayList<Pair> temp = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
                temp.add(new Pair(0, i));
            ArrayList<Integer> list = new ArrayList<>();
            if (map.containsKey(sum))
            {
                list = map.get(sum);
                for (int j = 0; j < list.size(); j++)
                {
                    temp.add(new Pair(list.get(j) + 1, i));
                }
            }
            list.add(i);
            map.put(sum, list);
        }
        return temp;
    }
    public static void print(ArrayList<Pair> result)
    {
        for (int i = 0; i < result.size(); i++)
        {
            Pair pair = result.get(i);
            System.out.println("Sub-Array found from "+ pair.start + " index to " + pair.end+" index");
        }
    }
    public static void main(String args[])
    {
        int[] arr = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
        int n = arr.length;

        ArrayList<Pair> result = getSubArray(arr, n);
        if (result.size() == 0)
            System.out.println("No such Sub-array exists");
        else
            print(result);
    }
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है।