Пронађите да ли постоји подред са 0 збиром


Ниво тешкоће Средњи
Често питани у Цитрик ДЕ Схав Голдман Сакс Заиста МакеМиТрип ОИО собе Паитм ТЦС
Ред Хасх

Проблем „Пронађи да ли постоји подниз са збројем 0“ наводи да сте добили цео број поредак који садрже и негативне целе бројеве. Изјава о проблему тражи да се утврди да ли је било који под-низ величине најмање 1. Овај под-низ треба да има збир једнак 1.

Пример

Пронађите да ли постоји подред са 0 збиром

arr[] = {2,1,-3,4,5}
yes

Објашњење

Овде елементи од индекса 0 до 2 имају збир 0.

arr[] = {4,1,-4,5,1}
yes

Објашњење

Не постоји под-низ који има збир 0.

Алгоритам

  1. Изјавите а Сет.
  2. Инитиализе збир да КСНУМКС.
  3. Пређите низ, док и <н (дужина низа).
    1. Додајте суму у арр [и] и сачувајте је у суми.
    2. Проверите да ли је испуњен било који од следећих услова:
      1. сум == 0 / арр [и] == 0 / ако Сет садржи вредност збира.
      2. ако је тачно, онда вратите тачно.
    3. Додајте збир у скуп.
  4. Ретурн фалсе.

Објашњење

Добили смо изјаву о проблему која тражи да сазнамо да ли постоји неки под-низ са сумом једнаком 0. Да бисмо то решили, користићемо скуп за решавање овог проблема. Спремићемо елементе датог низа у Сет. Затим истовремено додајте вредност у збир и проверите да ли постоји подударање под-низа са тренутним збиром у скупу или је сам збир једнак 0. Ако се утврди да постоји под-низ са збројем 0, вратићемо истинито.

Ако ниједан од под-низова не утврди да има зброј 0, тада ћемо из петље вратити фалсе. Такође, постоји једна ствар, ако је било који елемент 0, такође ћемо вратити труе јер је сам елемент под-низ једног појединачног елемента. Дакле, значи да смо пронашли један такав под-низ.

Овде у коду декларишемо логичку функцију, она ће вратити или труе или фалсе, ако је пронађен под-низ, враћа труе, иначе ће вратити фалсе.

Размотримо пример:

Пример

арр [] = {- 3,2,1,9,6}

Овде у коду ћемо прелазити низ и додавати сум и арр [и] и складиштити у сум и након те провере, ако је сум == 0 или арр [и] једнак 0 или Сет садржи вредност сум, ако је било који од задатих услова задовољен, вратићемо тачно, а затим додати збир у Сет.

Ако ниједан од под-низова није пронађен, вратићемо фалсе.

збир = 0, скуп = {}

и = 0, арр [и] = -3

сума = збир + арр [и] => 0 + - 3 = -3

ако је сум == 0 или арр [и] једнако 0 или Сет садржи вредност збира, три од њих су нетачна, па овде не радимо ништа и додамо -3 у Сет.

и = 1, арр [и] = 2

сума = сума + арр [и] => -3 + 2 = -1

ако је сум == 0 или арр [и] једнако 0 или Сет садржи вредност збира, три од њих су нетачна, па овде не радимо ништа и додамо -1 у Сет.

и = 2, арр [и] = 1

сума = сума + арр [и] => -1 + 1 = 0

ако је овде задовољен сум == 0, па враћамо труе, значи да смо пронашли под-низ са сумом 0.

Излаз: Да, постоји под-низ са сумом 0.

код

Ц ++ код за проналажење постоји ли подниз са збројем 0

#include<iostream>
#include<unordered_set>

using namespace std;

bool isSubArrayZero(int arr[], int n)
{
    unordered_set<int> Set;
    int sum = 0;
    for (int i = 0 ; i < n ; i++)
    {
        sum += arr[i];
        if (sum == 0 || Set.find(sum) != Set.end())
            return true;

        Set.insert(sum);
    }
    return false;
}
int main()
{
    int arr[] = {-3, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArrayZero(arr, n))
        cout << "Yes, a sub-array with sum 0 exist";
    else
        cout << "No, a sub-array with sum 0 does not exist";
    return 0;
}
Yes, a sub-array with sum 0 exist

Јава код за проналажење постоји ли подниз са збројем 0

import java.util.Set;
import java.util.HashSet;

class sumOfSubArrayZero
{
    public static Boolean isSubArrayZero(int arr[])
    {
        Set<Integer> set = new HashSet<Integer>();
        int Sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            Sum += arr[i];
            if (arr[i] == 0 || Sum == 0 || set.contains(Sum))
                return true;

            set.add(Sum);
        }
        return false;
    }
    public static void main(String arg[])
    {
        int arr[] = {-3, 2, 1, 9, 6};
        if (isSubArrayZero(arr))
            System.out.println("Yes, a subarray with sum 0 exists");
        else
            System.out.println("No, a subarray with sum 0 does not exist");
    }
}
Yes, a subarray with sum 0 exists

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

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

Он) где „Н“ је број елемената у низу. Све ово је било могуће због коришћења ХасхСет-а, јер нам омогућава да извршимо уметање, претраживање, брисање у О (1) времену.

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

Он) где „Н“ је број елемената у низу. С обзиром да у креираном хеш-скупу може бити највише н елемената, сложеност простора је линеарна.