Ҳама зергурӯҳҳоро бо 0 сум чоп кунед


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon FreeCharge Ҳақиқатан Маълумот Edge 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. Ҷамъи унсурҳои массивро бо баъзе тағирёбанда "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

Таҳлили мураккабӣ

Мураккабии вақт

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.