Бардык ич ара сүрөттөрдү 0 суммасы менен басып чыгарыңыз


Кыйынчылык деңгээли катуу
Көп суралган Amazon FreeCharge Чындыгында Info Edge Microsoft OYO бөлмөлөр
согуштук тизме таштанды

Сизге бүтүндөй массив берилген, сиздин милдетиңиз - сумма барабар болгон бардык суб-массивдерди басып чыгаруу 0. Бардык subarraysтарды 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

Algorithm

  1. 0 суммасы бар суб-массивге көз салуу үчүн, "Sum" деп аталган массив элементтеринин суммасын табыңыз.
  2. If сумма 0 деп табылса, ал мүмкүн болгон суб-массив 0ден учурдагы индекске чейин табылат.
  3. текшерүү, эгерде сумма жогорудагы процесстен табылган, биздин карта же жок.
  4. Эгерде картада сумма камтылса, анда ал мурунку суб-массивдин жалпы суммасы болгонун билдирет, эми ал учурдагы индекстерге чейин элементтин суммасы болуп калат.
  5. Эгер ал жок болсо, анда учурдагы сумманы Картага киргизиңиз.

түшүндүрүү

Биз колдоно турган болдук Хеширлөө анткени, муну менен биз суб-массивдерди жана алардын индекстерин көзөмөлдөй алабыз. Ошондой эле, биз ар кандай коллекцияларды колдонобуз. Алгач, массивдеги 0 суммасы менен мүмкүн болгон суб-массивдерди түзгөн бардык сандарды табышыбыз керек. Бул үчүн, биз массивдин элементтерин кошуп, аны кошуу үчүн сактайбыз. Бул сумма башталышында эле инициалдаштырылып жаткан.

Убактылуу суммасы ачкыч катары, вектору мааниси бар картаны түзөбүз. Ошентип, вектор бул жерде кириш башталгандагы элементтердин суммасы учурдагы суммага барабар болгон индекстерди билдирет.

Ушундан кийин, биз массивдин үстүнөн өтүп баштайбыз. Ошентип, алдыга жылган сайын, элементтерди өзгөрмө суммага кошуп турабыз. Эгерде сумма каалаган учурда 0 болуп табылат. Демек, бул башынан баштап суб-массивдин мааниси 0 дегенди билдирет, ошондой эле, эгерде кээ бир көрсөткүчтөр 0го барабар болгон болсо.

Эгерде сумма нөл деп табылбаса. Андан кийин Картада ошол сумма бар-жогун текшеребиз. Эгерде картада эсептелген сумма болбосо. Андан кийин учурдагы индексте аяктаган жана 0 суммасы бар бир дагы подразделение жок. Ошентип, учурдагы индексте аяктап, суммасы 0го барабар болгон бардык суб-массивдерди тапкандан кийин, учурдагы индексти векторго кошобуз учурдагы сумма ачкыч болгон карта.

Эгерде Картада сумма камтылса, анда биз буга чейин дагы ушундай эле суммага ээ болгон суб-массивдерди таптык. Анан ошол сумманын жана индекстин маанисин кошушубуз керек.

Мындан тышкары, биз вектор деп жарыялаган тизмебизди кайтарып беребиз. Ал жерден, эгерде кайтаруу мааниси 0 өлчөмүнө ээ болсо, анда биз эч нерсе чыкпагандыгын билдиребиз, анда басылып чыкпайт.

0 суммасы менен бардык субарнерлерди басып чыгаруу үчүн C ++ коду

#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 суммасы менен басып чыгаруу үчүн Java коду

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

Комплекстик анализ

Убакыт татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны.

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны.