Намерете дали има подмасив с сума 0  


Ниво на трудност M
Често задавани в Citrix DE Шоу Goldman Sachs Наистина MakeMyTrip OYO Стаи Paytm TCS
Array Хашиш

Проблемът „Намери дали има подмасив с 0 сума“ гласи, че сте получили цяло число масив съдържащи и отрицателни цели числа. Изявлението за проблем иска да се определи дали някой подмасив с размер е поне 1. Този подмасив трябва да има сума, равна на 1.

Пример  

Намерете дали има подмасив с сума 0

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

Обяснение

Тук елементите от индекс 0 до 2 имат сума 0.

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

Обяснение

Не съществува подмасив, който да има сума 0.

алгоритъм  

  1. Декларирайте а комплект.
  2. Инициализиране сума да 0.
  3. Прекоси масива, докато i <n (дължина на масива).
    1. Добавете сума към arr [i] и я съхранявайте към сума.
    2. Проверете дали някое от следните условия е вярно:
      1. sum == 0 / arr [i] == 0 / ако Set съдържа стойността на sum.
      2. ако е вярно, тогава върнете true.
    3. Добавете сумата към комплекта.
  4. Връщане на false.

Обяснение

Получихме изявление за проблем, което иска да разбере дали съществува някакъв подмасив със сума, равна на 0. За да разрешим това, ще използваме Set за решаване на този проблем. Ще съхраним елементите на даден масив в Set. След това едновременно добавете стойността в сумата и проверете дали има някакво съвпадение на под-масив с текущата сума в набора или самата сума е равна на 0. Ако се установи, че има под-масив със сума 0, ние ще се върнем вярно.

Ако нито един от под-масивите не е намерил сума 0, тогава ще върнем false извън цикъла. Също така, има едно нещо, ако някой от елементите е 0, тогава също ще върнем true, защото самият елемент е под-масив от един единствен елемент. Това означава, че сме намерили един такъв подмасив.

Вижте също
Числа с прости честоти, по-големи или равни на k

Тук в кода декларираме булева функция, тя ще върне или true, или false, ако е намерен подмасив, тя връща true, в противен случай ще върне false.

Нека разгледаме един пример:

Пример

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

Тук в кода ще прекосим масив и ще добавим sum и arr [i] и ще съхраняваме в sum и след тази проверка, ако sum == 0 или arr [i] е равно на 0 или Set съдържа стойността на sum, ако някое от даденото условие е изпълнено, тогава ще върнем true и след това ще добавим сума в Set.

Ако нито един от под-масива не бъде намерен, тогава ще върнем false.

сума = 0, набор = {}

i = 0, arr [i] = -3

сума = сума + arr [i] => 0 + - 3 = -3

ако sum == 0 или arr [i] е равно на 0 или Set съдържа стойността на sum, три от тях са фалшиви, така че не правим нищо тук и добавяме -3 в Set.

i = 1, arr [i] = 2

сума = сума + arr [i] => -3 + 2 = -1

ако sum == 0 или arr [i] е равно на 0 или Set съдържа стойността на sum, три от тях са фалшиви, така че не правим нищо тук и добавяме -1 в Set.

i = 2, arr [i] = 1

сума = сума + arr [i] => -1 + 1 = 0

ако тук е изпълнено условието sum == 0, така че връщаме true, това означава, че сме намерили подмасив със сума 0.

Изход: Да, съществува подмасив със сума 0.

код  

C ++ код, за да се намери дали има подмасив с сума 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

Java код за намиране, ако има подмасив с сума 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

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

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

О (п) където "н" е броят на елементите в масива. Всичко това беше възможно поради използването на HashSet, защото ни позволява да извършваме вмъкване, търсене, изтриване за O (1) време.

Вижте също
Най-доброто време за покупка и продажба на решение II Leetcode Solution

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

О (п) където "н" е броят на елементите в масива. Тъй като в създадения хеш може да има най-много n елемента, сложността на пространството е линейна.