Надрукуйце ўсе падмасівы з сумай 0


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка FreeCharge Сапраўды Інфармацыйны край Microsoft Нумары OYO
масіў гашыш

Вам дадзены цэлы масіў, ваша задача надрукаваць усе магчымыя падмасівы з сумай, роўнай 0. Такім чынам, нам трэба надрукаваць усе падмасівы з 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. Мы дадамо бягучы індэкс да вектара ў карта, якая мае бягучую суму ў якасці ключа.

Але калі Map змяшчае суму, гэта азначае, што мы знайшлі некалькі папярэдніх падмасіваў, якія мелі тую ж суму. Тады нам трэба скласці значэнне гэтай сумы і індэксаў.

І з гэтага мы вяртаем наш спіс, які мы абвясцілі вектарам. Адтуль, калі зваротнае значэнне мае памер 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

Код Java для друку ўсіх падмасіваў з сумай 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

Аналіз складанасці

Складанасць часу

Аб (п) дзе "П" - колькасць элементаў у масіве.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве.