Отпечатайте всички подредове с 0 суми


Ниво на трудност Трудно
Често задавани в Амазонка FreeCharge Наистина Info Edge Microsoft OYO Стаи
Array Хашиш

Получавате целочислен масив, вашата задача е да отпечатате всички възможни под-масиви със сума е равна на 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. Намерете сумата на елементите на масива с някаква променлива, кажете „Sum“, за да следите под-масива със сума 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

Анализ на сложността

Сложност във времето

О (п) където "н" е броят на елементите в масива.

Сложност на пространството

О (п) където "н" е броят на елементите в масива.